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]]