Transpose Matrix

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

O(m × n) : تُنسخ كل قيمة من القيم m × n مرة واحدة، ولا يمكن إنتاج الإجابة بأقل من ذلك. تشغل المصفوفة الجديدة مساحة O(m × n) ، أي بحجم الناتج نفسه.

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

بالنسبة إلى المصفوفة المربعة، نعم: بدّل matrix[i][j] مع matrix[j][i] لكل خلية فوق القطر، باستخدام ذاكرة إضافية O(1) . يتغير شكل المصفوفة غير المربعة، لذا تحتاج إلى مصفوفة جديدة عند استخدام قائمة من الصفوف.

مبتدئالمصفوفات والسلاسل النصية

+10

تحصل على مصفوفة من الأعداد الصحيحة على شكل قائمة من الصفوف: matrix[i][j] هي القيمة في الصف i، والعمود j. أعد مصفوفتها المنقولة: تنتقل القيمة الموجودة في الصف i، والعمود j إلى الصف j، والعمود i، بحيث يصبح كل صف عمودًا. ليس من الضروري أن تكون المصفوفة مربعة: فالمصفوفة m × n تصبح مصفوفة n × m.

الدالة

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

matrixinteger-2d-array: المصفوفة m × n، على هيئة قائمة تضم m صفوف، في كلٍّ منها n عددًا صحيحًا
تُرجعinteger-2d-array: منقول المصفوفة n × m، على هيئة قائمة من n صفوف، يحتوي كلٌّ منها على m عددًا صحيحًا

القيود

1 ≤ m, n ≤ 1000، حيث m = matrix.length وn = matrix[i].length
m × n ≤ 5000
كل صف له الطول نفسه n.
-1000 ≤ matrix[i][j] ≤ 1000

أمثلة

المدخلات: matrix = [[1, 2, 3], [4, 5, 6]]
المخرجات: [[1, 4], [2, 5], [3, 6]]
الشرح: يصبح الصف [1, 2, 3] العمود الأول، ويصبح [4, 5, 6] العمود الثاني. وعند القراءة صفًا صفًا، تكون النتيجة [1, 4]، [2, 5]، [3, 6]: مصفوفة 3 × 2.

سؤال إضافي

افترض أن المصفوفة مخزنة في مصفوفة مسطحة واحدة من القيم m × n، صفًا بعد صف. هل يمكنك إيجاد منقول مصفوفة غير مربعة داخل تلك المصفوفة، من دون استخدام مصفوفة ثانية؟

تلميحات

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

فُتح 0 من 3

الحل

لا يُجري تبديل الصفوف والأعمدة أي حسابات: تنتقل القيمة عند (i, j) إلى (j, i). العمل هنا هو تغيير الشكل. تتكوّن النتيجة من n صفوف، طول كلٍّ منها m، لذا لا يمكن تبديل صفوف قائمة غير مربعة في مكانها؛ أنشئ مصفوفة جديدة بالحجم المعكوس واملأها.

اقرأ المصفوفة عمودًا واحدًا في كل مرة

الفكرة

الصف j من الناتج هو العمود j من المُدخل، ويُقرأ من الأعلى إلى الأسفل. بالنسبة إلى [[1, 2, 3], [4, 5, 6]]، يُقرأ العمود 0 على الترتيب: 1 ثم 4، لذا يكون الصف الأول من الناتج هو [1, 4].

تُقرأ كل قيمة مرة واحدة وتُكتب مرة واحدة: زمن O(m × n)، ومساحة O(m × n) للناتج. يتخطى إنشاء كل صف جديد كل صفوف المُدخل بدلًا من القراءة على امتداد صف واحد، وهي الطريقة الأبطأ للتنقل في الذاكرة.

الخوارزمية

ليكن m عدد الصفوف وn طول الصف.
لكل عمود j من 0 إلى n-1، ابدأ بقائمة فارغة.
أضف matrix[i][j] إليها لكل i من 0 إلى m-1.
أضف القائمة إلى النتيجة بوصفها الصف j، وأعِد النتيجة بعد العمود الأخير.

def transpose(matrix):
    m, n = len(matrix), len(matrix[0])
    result = []
    for j in range(n):
        # Column j, read top to bottom, becomes row j of the answer.
        column = []
        for i in range(m):
            column.append(matrix[i][j])
        result.append(column)
    return result

املأ شبكة جديدة بحجم n × m عن طريق عكس كل خلية

الفكرة

أنشئ النتيجة n × m مسبقًا، ثم اقرأ المُدخلات بالترتيب المخزّنة فيه، صفًا تلو الآخر، وضع كل قيمة في موضعها المناظر: result[j][i] = matrix[i][j]. هذا صحيح لأن النقل هو بالضبط تبديل الفهارس هذا، مطبّقًا مرة واحدة على كل خلية.

تُنسخ كل قيمة مرة واحدة، لذا فالزمن هو O(m × n)، والشبكة تشغل مساحة O(m × n) التي يحتاج إليها الناتج على أي حال. والقراءة صفًا صفًا تزور الذاكرة بترتيب تخزينها، ويُخصَّص كل صف في النتيجة مرة واحدة بحجمه النهائي.

الخوارزمية

ليكن m عدد الصفوف، وn طول الصف.
أنشئ result بحيث يحتوي على n صفوف، ويضم كل صف m قيمة.
لكل صف i ولكل عمود j في المُدخل، عيّن result[j][i] = matrix[i][j].
أعِد result.

def transpose(matrix):
    m, n = len(matrix), len(matrix[0])
    # The answer has n rows of m values each.
    result = [[0] * m for _ in range(n)]
    for i in range(m):
        for j in range(n):
            result[j][i] = matrix[i][j]
    return result

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

إنشاء النتيجة بالشكل نفسه للمدخل. في المثال ذي الأبعاد 2 × 3، تؤدي كتابة result[2][0] إلى تجاوز النهاية: تحتاج النتيجة إلى n صفوف، طول كل منها m.
تبديل matrix[i][j] مع matrix[j][i] في مكانه. لا ينجح ذلك إلا عندما m = n، وفقط للخلايا التي تحقق j > i؛ فالتكرار على كل الخلايا يبدّل كل زوج مرتين ويعيد المصفوفة دون تغيير.
في Python، تنشئ [[0] * m] * n مراجع n إلى قائمة واحدة، لذا فإن كتابة خلية واحدة تكتب في عمود كامل. أنشئ كل صف على حدة.
في C، يقرأ المستدعي *returnSize على أنه عدد صفوف النتيجة، n، ويقرأ (*returnColumnSizes)[j] على أنه طول كل صف، m.

أسئلة شائعة3

ما هو منقول المصفوفة؟

هي المصفوفة التي تحصل عليها عند تبديل الصفوف والأعمدة: تنتقل القيمة في الصف i والعمود j إلى الصف j والعمود i. تصبح المصفوفة 2 × 3 مصفوفة 3 × 2، ويؤدي نقلها مرتين إلى استعادة المصفوفة الأصلية.

ما هو التعقيد الزمني لنقل المصفوفة؟

O(m × n): تُنسخ كل قيمة من القيم m × n مرة واحدة، ولا يمكن إنتاج الإجابة بأقل من ذلك. تشغل المصفوفة الجديدة مساحة O(m × n)، أي بحجم الناتج نفسه.

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

بالنسبة إلى المصفوفة المربعة، نعم: بدّل matrix[i][j] مع matrix[j][i] لكل خلية فوق القطر، باستخدام ذاكرة إضافية O(1). يتغير شكل المصفوفة غير المربعة، لذا تحتاج إلى مصفوفة جديدة عند استخدام قائمة من الصفوف.

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

اختبار #1

اختبار #2

وسيط

matrix = [[1, 2, 3], [4, 5, 6]]

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

[[1, 4], [2, 5], [3, 6]]