Product of Array Except Self

Q: למה חלוקה אינה מותרת במכפלת מערך ללא האיבר הנוכחי?

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

בינוניסכומי תחיליות

+10

ניתן לך מערך של מספרים שלמים nums. החזר מערך answer באותו אורך, שבו answer[i] הוא המכפלה של כל איבר ב-nums מלבד האיבר שבאינדקס i. בצע זאת בזמן O(n) ובלי להשתמש בחילוק.

פונקציה

productExceptSelf(nums: integer-array) → integer-array

numsinteger-array: מערך של מספרים שלמים, עם לפחות שני איברים
מחזירהinteger-array: מערך שהערך שלו באינדקס i הוא המכפלה של כל האיברים למעט nums[i]

אילוצים

2 ≤ nums.length ≤ 10⁴
-30 ≤ nums[i] ≤ 30
מכפלת כל הערכים שאינם אפס ב־nums נכנסת למספר שלם חתום בן 32 סיביות, ולכן גם כל מכפלה שתחשבו בדרך נכנסת בו.

דוגמאות

קלט: nums = [2, 3, 4, 5]
פלט: [60, 40, 30, 24]
הסבר: השמטת ה־2 משאירה 3 × 4 × 5 = 60, והשמטת ה־5 משאירה 2 × 3 × 4 = 24. שני האיברים האמצעיים פועלים באותו אופן: 2 × 4 × 5 = 40 ו־2 × 3 × 5 = 30.

+14 בדיקות נסתרות בשליחה

שאלת המשך

האם אפשר להשתמש רק ב־O(1) מקום נוסף, בלי לספור את המערך שמחזירים?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

המכפלה של כל הערכים פרט ל־nums[i] היא מכפלת הערכים שמשמאלו כפול מכפלת הערכים שמימינו. חלוקת המכפלה הכוללת ב־nums[i] נראית קצרה יותר, אבל היא אינה מותרת כאן, והיא נכשלת כשיש אפסים, כי אז המכפלה הכוללת היא 0. מכפלות קידומת וסיומת מחשבות כל מכפלה משמאל ומימין בשני מעברים, ולכן חישוב התשובה דורש זמן O(n). מערך הפלט יכול להכיל את המכפלות שמשמאל, ומשתנה אחד מחזיק את המכפלה שמימין, כך שאין צורך במערך נוסף.

כפלו את האחרים עבור כל אינדקס

נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר

האינטואיציה

פעל לפי ההגדרה. עבור כל אינדקס i, התחל מכפלה ב-1 וכפול בה כל nums[j] שעבורו האינדקס j אינו i. דילוג על האינדקס הזה, במקום לחלק בו בהמשך, משאיר את האפסים חסרי השפעה: ב-[-2, 5, 0, 3] המכפלה עבור אינדקס 2 אף פעם לא כוללת את 0, ומתקבלת התוצאה -30.

הפתרון נכון, אבל הוא חוזר על עבודה. המכפלות עבור אינדקס 0 ועבור אינדקס 1 חולקות את כל הערכים מלבד שניים, ובכל זאת מכפילים את כולם שוב. עבור כל אחת מ-n העמדות נדרשות n-1 פעולות כפל, כ-10^8 בסך הכול כאשר n = 10^4. שפת C מצליחה לבצע זאת בתוך שבריר שנייה, אבל Python, Ruby או R נמשכות הרבה יותר מדי זמן.

אלגוריתם

צרו מערך תשובות באורך n.
עבור כל אינדקס i, הגדירו את product ל-1.
הכפילו את product בכל nums[j] שהאינדקס j שלו אינו i.
שמרו את product באינדקס i של התשובה.
החזירו את התשובה.

def productExceptSelf(nums):
    n = len(nums)
    answer = []
    for i in range(n):
        product = 1
        for j in range(n):
            if j != i:
                product *= nums[j]
        answer.append(product)
    return answer

מערכי מכפלה של תחיליות וסיומות

האינטואיציה

פצלו את המכפלה עבור האינדקס i לשניים: הערכים שלפני i והערכים שאחריו. קראו למכפלות האלה before[i] ו-after[i]. ואז answer[i] = before[i] × after[i], ומשאירים את nums[i] בחוץ בלי לבצע חילוק.

כל מערך גדל מתוך השכן שלו בעזרת כפל אחד. before[0] הוא 1, המכפלה של אפס ערכים, ו-before[i] = before[i-1] × nums[i-1]. מהקצה השני, after[n-1] הוא 1 ו-after[i] = after[i+1] × nums[i+1]. עבור [2, 3, 4, 5] מתקבלים before = [1, 2, 6, 24] ו-after = [60, 20, 5, 1], וכפל שלהם איבר מול איבר נותן [60, 40, 30, 24].

שלושה מעברים של n צעדים נותנים זמן O(n). שתי מערכי העזר צורכים זיכרון נוסף של O(n), שאותו הגישה הבאה מבטלת.

אלגוריתם

מלאו את before משמאל: before[0] = 1, ואז כל איבר הוא האיבר הקודם כפול הערך הקודם.
מלאו את after מימין: after[n-1] = 1, ואז כל איבר הוא האיבר הבא כפול הערך הבא.
הגדירו את answer[i] בתור before[i] × after[i] עבור כל אינדקס.
החזירו את answer.

def productExceptSelf(nums):
    n = len(nums)
    # before[i] = product of nums[0..i-1], after[i] = product of nums[i+1..n-1]
    before = [1] * n
    after = [1] * n
    for i in range(1, n):
        before[i] = before[i - 1] * nums[i - 1]
    for i in range(n - 2, -1, -1):
        after[i] = after[i + 1] * nums[i + 1]
    return [before[i] * after[i] for i in range(n)]

מכפלות שנותרו בתשובה, מכפלה אחת מתבצעת מימין

האינטואיציה

לעולם אין צורך בכל מערך ה־after בבת אחת. כשמתקדמים מהקצה הימני, מכפלת הערכים שמימין ל־i היא מספר יחיד. שמרו אותו במשתנה right ועדכנו אותו בכפל אחד בכל צעד.

לכן כתבו את המכפלות משמאל ישירות לתוך מערך התשובה במעבר הראשון. במעבר השני, מימין, הכפילו את answer[i] ב־right, ורק אז הכפילו את right ב־nums[i]. הסדר חשוב: כשמשתמשים ב־right באינדקס i, הוא עדיין לא אמור לכלול את nums[i].

עבור [2, 3, 4, 5], המעבר הראשון משאיר את [1, 2, 6, 24]. במעבר השני משתמשים ב־right = 1, 5, 20, 60 באינדקסים 3, 2, 1, 0, והמערך הופך ל־[60, 40, 30, 24]. זמן הריצה עדיין O(n), ומלבד המערך שמוחזר, הזיכרון הנוסף הוא משתנה אחד: O(1).

אלגוריתם

הגדר את answer[0] = 1, ואז משמאל לימין הגדר את answer[i] = answer[i-1] × nums[i-1].
הגדר את right ל־1.
מהאינדקס האחרון ועד 0, הכפל את answer[i] ב־right.
לאחר מכן הכפל את right ב־nums[i].
החזר את answer.

def productExceptSelf(nums):
    n = len(nums)
    # Pass 1: answer[i] = product of everything left of i
    answer = [1] * n
    for i in range(1, n):
        answer[i] = answer[i - 1] * nums[i - 1]
    # Pass 2: multiply in the product of everything right of i
    right = 1
    for i in range(n - 1, -1, -1):
        answer[i] *= right
        right *= nums[i]
    return answer

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

השגיאות כאן נובעות מאפסים, מסדר שתי העדכונים במעבר השני ומקצות המערך.

חלוקת המכפלה הכוללת ב־nums[i] נכשלת ברגע שמופיע 0. עבור [-2, 5, 0, 3] המכפלה הכוללת היא 0, ובאינדקס 2 יהיה צורך לחשב 0 חלקי 0. אפשר לטפל בכך באמצעות ספירת האפסים, אבל הבעיה אוסרת על חלוקה בכל מקרה.
כפל right ב־nums[i] לפני שמשתמשים בו מכניס את nums[i] למכפלה של עצמו. עבור [2, 3, 4, 5] הערך האחרון הופך ל־120 במקום ל־24.
התחלת מכפלות הצד השמאלי ב־nums[0] במקום ב־1. אין ערכים משמאל לאינדקס 0, לכן מכפלת הצד השמאלי היא המכפלה הריקה, 1, ו־answer[0] מסתיים כמכפלת הערכים שמימינו בלבד.
גבולות הלולאה: המעבר השמאלי קורא את nums[i-1], ולכן מתחיל באינדקס 1. מערך סיומות קורא את nums[i+1], ולכן מתחיל באינדקס n-2.
שני אפסים הופכים כל תשובה ל־0. אפס אחד הופך כל תשובה ל־0, מלבד זו שבאינדקס של האפס עצמו. בדקו את שני המקרים לפני שאתם סומכים על הקוד שלכם.

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

מהי סיבוכיות הזמן של מכפלת המערך מלבד האיבר עצמו?

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

למה חלוקה אינה מותרת במכפלת מערך ללא האיבר הנוכחי?

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

האם מערך הפלט נחשב לשטח נוסף?

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

איך Product of Array Except Self מטפל באפסים?

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

Python

def productExceptSelf(nums):
    # כתבו כאן את הקוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

nums = [2, 3, 4, 5]

צפוי

[60, 40, 30, 24]

Product of Array Except Self

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

כפלו את האחרים עבור כל אינדקס

מערכי מכפלה של תחיליות וסיומות

מכפלות שנותרו בתשובה, מכפלה אחת מתבצעת מימין

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

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

בעיות דומות