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