Transpose Matrix

Q: מהי המטריצה הטרנספוזיצית של מטריצה?

זו המטריצה שמתקבלת מהחלפת השורות והעמודות: הערך בשורה i , בעמודה j עובר לשורה j , לעמודה i . מטריצה בגודל 2 × 3 הופכת למטריצה בגודל 3 × 2 , והתמרה פעמיים מחזירה את המטריצה המקורית.

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