Set Matrix Zeroes

Q: מהי סיבוכיות הזמן של איפוס אפסים במטריצה?

‏O(m·n) עבור מטריצה בגודל m × n , מכיוון שכל תא נקרא ונכתב מספר קבוע של פעמים. אין פתרון יעיל יותר, כי כל תא שדילגו עליו יכול להיות ה־0 שמשנה את התשובה. המקום הנוסף הוא O(m + n) עם מערכי סימון ו־O(1) כאשר משתמשים בשורה הראשונה ובעמודה הראשונה כסמנים.

בינונימערכים ומחרוזות גיבוב

+10

הקלט הוא רשת m × n של מספרים שלמים, הנתונה שורה אחר שורה, כך ש־matrix[i][j] נמצא בשורה i ובעמודה j. בכל מקום שבו יש ברשת 0, יש להגדיר את כל אותה שורה ואת כל אותה עמודה כ־0. רק האפסים שהיו קיימים בתחילת הדרך נחשבים: תא שמשנים ל־0 אינו מאפס את השורה או העמודה שלו. מותר לשנות את הרשת במקום; יש להחזיר אותה.

פונקציה

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

matrixinteger-2d-array: רשת של מספרים שלמים, רשימה פנימית אחת לכל שורה
מחזירהinteger-2d-array: המטריצה שבה כל שורה וכל עמודה שהכילו 0 נקבעו ל־0

אילוצים

m == matrix.length וגם n == matrix[i].length
1 ≤ m, n ≤ 1000 וגם m × n ≤ 5000
כל השורות m מכילות n ערכים.
-1000 ≤ matrix[i][j] ≤ 1000

דוגמאות

קלט: matrix = [[3, 8, 1], [5, 0, 7], [2, 6, 4]]
פלט: [[3, 0, 1], [0, 0, 0], [2, 0, 4]]
הסבר: ה־0 היחיד נמצא בשורה 1, בעמודה 1. כל הערכים בשורה 1 הופכים ל־0, וכך גם כל הערכים בעמודה 1, מה שהופך את ה־8 וה־6 ל־0. ארבע הפינות אינן נמצאות באף אחד מהקווים ושומרות על הערכים שלהן.

שאלת המשך

הגישה הטובה ביותר בהמשך שומרת שני ערכים בוליאניים נוספים. האם אפשר להסתפק באחד, ולתת ל־matrix[0][0] לייצג את השורה הראשונה?

פתרון

0 שאתה כותב נראה בדיוק כמו 0 שקיבלת, ולכן איפוס שורות במהלך הסריקה מפזר אפסים ברחבי המטריצה. הפרד בין הקריאה לכתיבה: תחילה תעד אילו שורות ועמודות הכילו 0, ואז אפס אותן. שמור את התיעוד הזה בשני מערכים, או, כדי להשתמש ב-O(1) מקום נוסף, בשורה הראשונה ובעמודה הראשונה של המטריצה עצמה.

סמנו שורות ועמודות בשני מערכים

האינטואיציה

תא הופך ל־0 בדיוק כאשר השורה שלו או העמודה שלו הכילו 0 בתחילת הדרך. לכן תעדו שתי רשימות של עובדות, zeroRow[i] ו־zeroCol[j], במעבר שאינו כותב, ואז אפסו כל תא שהשורה או העמודה שלו מסומנות. שום דבר לא מתפשט, כי כל הקריאות מתבצעות לפני הכתיבה הראשונה.

כל מעבר מבקר בכל אחד מ־m·n התאים פעם אחת, ולכן זמן הריצה הוא O(m·n), והמערכים מכילים m + n ערכים בוליאניים.

אלגוריתם

צרו את zeroRow עם m איברים ואת zeroCol עם n איברים, כשכולם false.
סרקו כל תא. כאשר matrix[i][j] הוא 0, הגדירו את zeroRow[i] ואת zeroCol[j] לערך true.
סרקו שוב כל תא והגדירו אותו ל־0 כאשר zeroRow[i] או zeroCol[j] הוא true.
החזירו את המטריצה.

def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    zero_row = [False] * m
    zero_col = [False] * n
    # Pass 1: only read, so a new zero can never spread further.
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == 0:
                zero_row[i] = True
                zero_col[j] = True
    # Pass 2: write.
    for i in range(m):
        for j in range(n):
            if zero_row[i] or zero_col[j]:
                matrix[i][j] = 0
    return matrix

השתמשו בשורה הראשונה ובעמודה הראשונה כסמנים

האינטואיציה

בעמודה הראשונה יש תא אחד לכל שורה, ובשורה הראשונה תא אחד לכל עמודה — אלה הצורות של שני מערכי הסמנים. לכן 0 בשורה i, בעמודה j, כותב 0 לתוך matrix[i][0] ולתוך matrix[0][j]. כך לא מאבדים מידע: כל אחד מהתאים האלה נמצא בשורה או בעמודה שבכל מקרה צריכות להפוך ל-0.

שורה 0 ועמודה 0 הן גם נתונים וגם סמנים, וסמן בהן מסתיר אם היה בהן 0 משלהן. לכן יש לבדוק אותן תחילה ולשמור את התשובות בשני ערכים בוליאניים. יש לסמן ולאפס רק תאים שעבורם i ≥ 1 וגם j ≥ 1, ולאפס את שורה 0 ואת עמודה 0 בסוף, כי המילוי קורא מהן.

בדוגמה השנייה, הערך 3 בשורה 1, בעמודה 1, נשאר ללא שינוי כי הסמנים שלו, matrix[1][0] = 9 ו-matrix[0][1] = 4, אינם 0. זמן הריצה נשאר O(m·n), עם שני ערכים בוליאניים של זיכרון נוסף (O(m·n) ב-R, שמעתיקה תחילה את הקלט).

אלגוריתם

הגדר את firstRowZero אם בשורה 0 מופיע 0, ואת firstColZero אם בעמודה 0 מופיע 0.
עבור כל תא שמקיים i ≥ 1 ו-j ≥ 1 ומכיל 0, הגדר את matrix[i][0] ואת matrix[0][j] ל-0.
עבור כל תא שמקיים i ≥ 1 ו-j ≥ 1, הגדר אותו ל-0 כאשר matrix[i][0] או matrix[0][j] הוא 0.
אם firstRowZero מוגדר, הגדר את שורה 0 ל-0. אם firstColZero מוגדר, הגדר את עמודה 0 ל-0.
החזר את המטריצה.

def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    # The first row and column will hold the markers, so remember first
    # whether they need to become zero themselves.
    first_row_zero = any(matrix[0][j] == 0 for j in range(n))
    first_col_zero = any(matrix[i][0] == 0 for i in range(m))
    # Mark: a zero inside the matrix flags its row in column 0
    # and its column in row 0.
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][j] == 0:
                matrix[i][0] = 0
                matrix[0][j] = 0
    # Fill the inside from the markers.
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0
    # The marker row and column go last.
    if first_row_zero:
        for j in range(n):
            matrix[0][j] = 0
    if first_col_zero:
        for i in range(m):
            matrix[i][0] = 0
    return matrix

מלכודות ומקרי קצה

איפוס של שורה ועמודה ברגע שמוצאים 0. בדוגמה הראשונה, ה־0 החדש בשורה 1, עמודה 2 מאפס לאחר מכן את עמודה 2, ורק ה־3 בפינה השמאלית העליונה נשאר.
מתן אפשרות ל־matrix[0][0] לסמן גם את שורה 0 וגם את עמודה 0. ב־[[1, 2, 3], [0, 5, 6], [7, 8, 9]] ה־0 בעמודה 0 מאפס לאחר מכן בטעות את שורה 0.
איפוס של שורה 0 או עמודה 0 לפני המילוי. ב־[[0, 2, 3], [4, 5, 6], [7, 8, 9]] כל העמודות נראות לאחר מכן מסומנות, וכל המטריצה הופכת ל־0.
שכחה של שורות בודדות. כשיש שורה אחת, הלולאות שמתחילות ב־1 לא עושות דבר, והערכים הבוליאניים עושים את כל העבודה: [[1, 0, 3]] חייבת להפוך ל־[[0, 0, 0]].

שאלות נפוצות3

למה אי אפשר להציב את האפסים בזמן שסורקים את המטריצה?

ה־0 שאתה כותב נראה כמו 0 מקורי. כשהסריקה מגיעה אליו, הוא מנקה את השורה ואת העמודה שלו, והאפסים החדשים האלה מתפשטים הלאה. תעד כל 0 מקורי לפני שאתה משנה תא כלשהו.

מהי סיבוכיות הזמן של איפוס אפסים במטריצה?

‏O(m·n) עבור מטריצה בגודל m × n, מכיוון שכל תא נקרא ונכתב מספר קבוע של פעמים. אין פתרון יעיל יותר, כי כל תא שדילגו עליו יכול להיות ה־0 שמשנה את התשובה. המקום הנוסף הוא O(m + n) עם מערכי סימון ו־O(1) כאשר משתמשים בשורה הראשונה ובעמודה הראשונה כסמנים.

האם אפשר לסמן תאים בערך מיוחד במקום 0?

חלק מהפתרונות כותבים סמן מקום בתאים שיש לנקות והופכים את סמני המקום לאפסים בסוף. זה עובד רק אם סמן המקום לעולם לא יכול להופיע בקלט, דבר שמטריצה של מספרים שלמים כמעט אף פעם לא מבטיחה. כתיבת הסמן לאורך שורה ועמודה עבור כל 0 עולה גם זמן O(m·n·(m + n)).

def setZeroes(matrix):
    # כתבו כאן את הקוד

בדיקה #1

בדיקה #2

ארגומנט

matrix = [[3, 8, 1], [5, 0, 7], [2, 6, 4]]

הפלט הצפוי

[[3, 0, 1], [0, 0, 0], [2, 0, 4]]