Transpose Matrix
تحصل على مصفوفة من الأعداد الصحيحة على شكل قائمة من الصفوف: matrix[i][j] هي القيمة في الصف i، العمود j. أعد منقولها، أي المصفوفة الناتجة عن تحويل كل صف إلى عمود. تنتقل القيمة الموجودة في الصف i، العمود j إلى الصف j، العمود i. ليس من الضروري أن تكون المصفوفة مربعة: فالمصفوفة ذات الأبعاد m × n تصبح مصفوفة ذات الأبعاد n × m.
الدالة
- matrixinteger-2d-array
- المصفوفة m × n، على شكل قائمة من m صفوف، يحتوي كلٌّ منها على n عددًا صحيحًا
- تُرجعinteger-2d-array
- منقول مصفوفة أبعادها n × m، على شكل قائمة تضم n صفوف، في كل منها m أعداد صحيحة
القيود
1 ≤ m, n ≤ 1000، حيثm = matrix.lengthوn = matrix[i].lengthm × 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]: تحولت المصفوفة ذات الأبعاد 2 × 3 إلى مصفوفة ذات الأبعاد 3 × 2.
- المدخلات
- matrix = [[1, 2], [3, 4]]
- المخرجات
- [[1, 3], [2, 4]]
- الشرح
- في مصفوفة مربعة، تظل القيمتان القطريتان 1 و4 في موضعيهما، وتتبادل القيمتان خارج القطر موضعيهما: تنتقل 2 من الصف 0، العمود 1 إلى الصف 1، العمود 0، وتنتقل 3 في الاتجاه المعاكس.
+15 اختبارات مخفية عند الإرسال
سؤال إضافي
افترض أن المصفوفة مخزّنة في مصفوفة مسطّحة واحدة تضم m × n قيمة، صفًّا بعد صف. هل يمكنك تبديل صفوف وأعمدة مصفوفة غير مربعة داخل تلك المصفوفة، من دون استخدام مصفوفة ثانية؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
إذا كان للإدخال
mصفوف وnأعمدة، فكم عدد الصفوف والأعمدة في الإجابة؟قارن موضع القيمة قبل العملية وبعدها: القيمة في الصف
iوالعمودjينتهي بها الأمر في الصفjوالعمودi.أنشئ نتيجةً تتكوّن من
nصفوف، يحتوي كلٌّ منها علىmقيمة، ثم كرّر المرور على كل خلية في المُدخل وانسخmatrix[i][j]إلىresult[j][i].
الحل
تبديل الصفوف والأعمدة هو مجرد تغيير لموضع القيمة: تنتقل القيمة عند (i, j) إلى (j, i)، ولا يُجرى أي حساب. المطلوب هو ضبط الأبعاد بالشكل الصحيح. لا يمكن تبديل صفوف مصفوفة غير مربعة مخزنة في قائمة داخل المصفوفة نفسها، لأن الناتج يتكون من n صفوف طول كل منها m بدلًا من m صفوف طول كل منها n، لذا تنشئ مصفوفة جديدة بأبعاد معكوسة وتملؤها.
اقرأ المصفوفة عمودًا واحدًا في كل مرة
الفكرة
الصف j من الناتج هو العمود j من المُدخل، مقروءًا من الأعلى إلى الأسفل. لذا أنشئ الناتج صفًا تلو الآخر: لكل عمود j من 0 إلى n-1، اجمع matrix[0][j] وmatrix[1][j]، وهكذا نزولًا حتى matrix[m-1][j]، ثم أضف تلك القائمة بوصفها الصف التالي.
في [[1, 2, 3], [4, 5, 6]]، يُقرأ العمود 0: 1 ثم 4، والعمود 1: 2 ثم 5، والعمود 2: 3 ثم 6. الناتج هو [[1, 4], [2, 5], [3, 6]]، ويتكوّن من n = 3 صفوف، في كل منها m = 2 من القيم.
تُقرأ كل قيمة مرة واحدة وتُكتب مرة واحدة، لذا فإن الزمن هو 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].
القاعدة صحيحة لأن التبديل هو بالضبط تبديل الفهرسين. في المثال المربّع [[1, 2], [3, 4]]، يبقى العددان 1 و4 على القطر في موضعيهما، وينتقل 2 من (0, 1) إلى (1, 0)، وينتقل 3 من (1, 0) إلى (0, 1)، فنحصل على [[1, 3], [2, 4]].
تُنسخ كل واحدة من القيم m × n مرة واحدة، لذا يكون الزمن 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
أخطاء شائعة وحالات حدّية
تأتي معظم الإجابات الخاطئة من شكل المصفوفة، لا من القيم.
- إنشاء النتيجة بالشكل الأصلي. لا تعمل نتيجة تتكون من
mصفوف وnأعمدة إلا مع مُدخل مربع؛ ففي المثال ذي الأبعاد 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.
أسئلة شائعة4
ما هو منقول المصفوفة؟
هي المصفوفة التي تحصل عليها بتبديل الصفوف والأعمدة: تنتقل القيمة الموجودة في الصف i والعمود j إلى الصف j والعمود i. تصبح المصفوفة 2 × 3 بحجم 3 × 2، ويؤدي إجراء النقل مرتين إلى استعادة المصفوفة الأصلية.
ما هو التعقيد الزمني لنقل مصفوفة؟
إنه O(m × n)، لأن كل قيمة من القيم m × n تُنسخ مرة واحدة، ولا يمكن إنتاج النتيجة بأقل من ذلك. تشغل المصفوفة الجديدة مساحة O(m × n)، وهو حجم الناتج نفسه.
هل يمكنك تبديل صفوف المصفوفة وأعمدتها في مكانها؟
بالنسبة إلى مصفوفة مربعة، نعم: بدّل matrix[i][j] مع matrix[j][i] لكل خلية فوق القطر، باستخدام ذاكرة إضافية O(1). أما المصفوفة غير المربعة، فتكون النتيجة ذات شكل مختلف، لذا تحتاج إلى مصفوفة جديدة عند استخدام قائمة من الصفوف.
كيف يمكنك تبديل صفوف وأعمدة مصفوفة غير مربعة؟
أنشئ نتيجةً تحتوي على n صفوف، طول كلٍّ منها m، بينما يحتوي الإدخال على m صفوف، طول كلٍّ منها n. ثم انسخ كل قيمة باستخدام result[j][i] = matrix[i][j]. لا تنطبق فكرة القطر في حالة المصفوفة المربعة هنا، لأن المصفوفتين لا تتشاركان الشكل نفسه.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def transpose(matrix):
# اكتب الكود هناالحالة 1
الحالة 2
المدخلات
matrix = [[1, 2, 3], [4, 5, 6]]
المتوقع
[[1, 4], [2, 5], [3, 6]]