Rotate Image

Q: ما التعقيد الزمني وتعقيد المساحة لتدوير مصفوفة؟

يستغرق تدوير مصفوفة n × n زمنًا قدره O(n²)، لأن كل قيمة تقريبًا يجب أن تتحرك مرة واحدة. تحتاج طريقة النقل ثم العكس إلى مساحة إضافية قدرها O(1). كما يستغرق إنشاء نسخة مدوّرة زمنًا قدره O(n²)، لكنه يستخدم مساحة إضافية قدرها O(n²).

Q: هل يمكنك تدوير مصفوفة عن طريق نقل أربع قيم في كل مرة؟

نعم. تنتمي كل قيمة خارج المركز إلى دورة من أربع خلايا: (i, j) ، و (j, n-1-i) ، و (n-1-i, n-1-j) ، و (n-1-j, i) . عالج كل حلقة على حدة، واحتفظ بقيمة واحدة من كل دورة في متغير، ثم أزِح القيم الثلاث الأخرى. لها التعقيد الزمني نفسه O(n²) والمساحة O(1)، مع مزيد من حسابات الفهارس التي يمكن أن تخطئ فيها.

متوسطالمصفوفات والسلاسل النصية رياضيات ومحاكاة

+10

أُعطيت شبكة n × n من الأعداد الصحيحة، على شكل قائمة لكل صف. أدرها ربع دورة باتجاه عقارب الساعة وأعِدها. يصبح الصف العلوي العمود الأيمن، ويصبح الصف الثاني العمود الذي على يساره، وهكذا: تنتقل القيمة عند (i, j) إلى (j, n-1-i). يمكنك تعديل الشبكة في مكانها؛ أَعِدها.

الدالة

rotateImage(matrix: integer-2d-array) → integer-2d-array

matrixinteger-2d-array: الشبكة المربعة، قائمة داخلية واحدة لكل صف
تُرجعinteger-2d-array: دارت المصفوفة 90 درجة باتجاه عقارب الساعة

القيود

n == matrix.length == matrix[i].length
1 ≤ n ≤ 70
-1000 ≤ matrix[i][j] ≤ 1000

أمثلة

المدخلات: matrix = [[3, 7, 1], [9, 5, 2], [4, 8, 6]]
المخرجات: [[4, 9, 3], [8, 5, 7], [6, 2, 1]]
الشرح: يصبح الصف الأول، 3 7 1، العمود الأخير عند قراءته من الأعلى إلى الأسفل. ويصبح العمود الأول، 3 9 4، عند قراءته من الأسفل إلى الأعلى، الصف الأول [4, 9, 3]. وتبقى القيمة الوسطى 5 في مكانها.

سؤال إضافي

ما الخطوتان الموضعيّتان اللتان تديران المصفوفة 180 درجة، وهل يمكنك فعل ذلك بتمريرة واحدة من عمليات التبديل؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

موضع انتقال كل قيمة تحدده صيغة: تنتقل (i, j) إلى (j, n-1-i). تكمن الصعوبة في نقل القيم من دون مصفوفة ثانية، لأن كتابة قيمة في خليتها الجديدة تستبدل قيمة لم تُنقل بعد. إن إجراء تبديل المحاور ثم عكس الصفوف يُنتج ربع دورة الاتجاه نفسها من تبديلات الأزواج.

أنشئ نسخة مُدارة

الفكرة

يصبح الصف i العمود n-1-i، وتنتقل القيمة عند الموضع j في الصف إلى الموضع j نزولًا في ذلك العمود، أي إلى الصف j. لذا result[j][n-1-i] = matrix[i][j]. في المثال الأول، تنتقل القيمة 4 من الصف 2 والعمود 0 إلى الصف 0 والعمود 0، ولهذا تبدأ الإجابة بـ 4.

تتحرك القيم ضمن دورات من أربعة مواضع، لذا فإن الكتابة في المكان نفسه ستمحو قيمة قبل أن تنتقل: ستكتب القيمة 3 فوق القيمة 1 في الزاوية العلوية اليمنى. يتطلب النسخ n² خلايا إضافية، أي 4,900 عندما تكون n = 70.

الخوارزمية

أنشئ مصفوفة ناتجة n × n.
لكل صف i وعمود j، انسخ matrix[i][j] إلى result[j][n-1-i].
أعِد النتيجة.

def rotateImage(matrix):
    n = len(matrix)
    result = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            # Row i becomes column n-1-i, read from top to bottom.
            result[j][n - 1 - i] = matrix[i][j]
    return result

انقل الصفوف إلى الأعمدة، ثم اعكس ترتيب عناصر كل صف

الفكرة

ينقل التحويل إلى المصفوفة المنقولة (i, j) إلى (j, i)، ويؤدي عكس الصف إلى نقل العمود c إلى العمود n-1-c. معًا، ينقلان (i, j) إلى (j, n-1-i)، وهو الموضع الذي يضعه فيه الدوران تمامًا.

تُنفَّذ العمليتان في المكان لأن كلًّا منهما مجموعة من عمليات تبديل الأزواج. في التحويل إلى المصفوفة المنقولة، يجب أن يكون كلٌّ من matrix[i][j] وmatrix[j][i] في خلية الآخر، لذا يكفي تبديل واحد لإتمام الأمر. بدّل الأزواج التي تحقق j > i فقط، وإلا فسيُعاد تبديل كل زوج إلى موضعه الأصلي. يعكس الصف تبديل طرفيه والتحرك نحو الوسط.

في المثال الأول، ينتج عن التحويل إلى المصفوفة المنقولة [[3, 9, 4], [7, 5, 8], [1, 2, 6]]: يحتوي كل صف الآن على عمود سابق. ويؤدي عكس كل صف إلى النتيجة المطلوبة.

ينفّذ التحويل إلى المصفوفة المنقولة n(n-1)/2 عملية تبديل، وتنفّذ عمليات العكس n·⌊n/2⌋ عملية، لذا يكون العمل O(n²) مع استخدام بضعة متغيرات من الذاكرة الإضافية. ينسخ إصدار R المدخل أولًا إلى مصفوفة R، لذا تبلغ ذاكرته الإضافية O(n²).

الخوارزمية

لكل خلية فوق القطر الرئيسي، (i, j) مع j > i، بدّل قيمتها مع قيمة الخلية (j, i).
في كل صف، بدّل القيمتين الأولى والأخيرة، وحرّك الطرفين نحو الداخل حتى يلتقيا.
أعِد المصفوفة.

def rotateImage(matrix):
    n = len(matrix)
    # Transpose: swap each value above the diagonal with its mirror below it.
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    # Reverse each row with two pointers.
    for row in matrix:
        left, right = 0, n - 1
        while left < right:
            row[left], row[right] = row[right], row[left]
            left += 1
            right -= 1
    return matrix

أخطاء شائعة وحالات حدّية

إجراء النقل مع بدء j من 0. يُبدَّل كل زوج مرتين، ما يلغي النقل، لذا تكون النتيجة عكس الصفوف فقط، كأنها صورة مرآة.
عكس المصفوفة قبل نقلها. هذا الترتيب يدير المصفوفة عكس اتجاه عقارب الساعة. يكشف اختبار بمصفوفة 2 × 2 هذا الخطأ: يجب أن تصبح [[1, 2], [3, 4]] هكذا: [[3, 1], [4, 2]].
كتابة matrix[j][n-1-i] = matrix[i][j] في المصفوفة نفسها. ما تزال الخلية المستهدفة تحتوي على قيمة لم تُنقل، وستُفقد.
استخدام n-i بدلًا من n-1-i. عند استخدام فهارس تبدأ من 0، يكون العمود الأخير هو n-1، لذا تتجاوز n-i نهاية المصفوفة عندما تكون i = 0.

أسئلة شائعة3

ما التعقيد الزمني وتعقيد المساحة لتدوير مصفوفة؟

يستغرق تدوير مصفوفة n × n زمنًا قدره O(n²)، لأن كل قيمة تقريبًا يجب أن تتحرك مرة واحدة. تحتاج طريقة النقل ثم العكس إلى مساحة إضافية قدرها O(1). كما يستغرق إنشاء نسخة مدوّرة زمنًا قدره O(n²)، لكنه يستخدم مساحة إضافية قدرها O(n²).

كيف تدوّر مصفوفة عكس اتجاه عقارب الساعة؟

بدّل ترتيب الخطوتين: اعكس كل صف أولًا، ثم انقل المصفوفة. يمكنك أيضًا نقل المصفوفة ثم عكس ترتيب الصفوف. في كلتا الحالتين، تنتهي القيمة عند (i, j) في الموضع (n-1-j, i).

هل يمكنك تدوير مصفوفة عن طريق نقل أربع قيم في كل مرة؟

نعم. تنتمي كل قيمة خارج المركز إلى دورة من أربع خلايا: (i, j)، و(j, n-1-i)، و(n-1-i, n-1-j)، و(n-1-j, i). عالج كل حلقة على حدة، واحتفظ بقيمة واحدة من كل دورة في متغير، ثم أزِح القيم الثلاث الأخرى. لها التعقيد الزمني نفسه O(n²) والمساحة O(1)، مع مزيد من حسابات الفهارس التي يمكن أن تخطئ فيها.

def rotateImage(matrix):
    # اكتب الكود هنا

اختبار #1

اختبار #2

وسيط

matrix = [[3, 7, 1], [9, 5, 2], [4, 8, 6]]

الإخراج المتوقع

[[4, 9, 3], [8, 5, 7], [6, 2, 1]]