חידה תכנותית: מכפלת כל הפריטים במערך מלבד הנוכחי

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

לדוגמה:

Input = [3,2,5]
Output = [10, 15, 6]

דוגמה נוספת:

Input = [1,-2,0,3]
Output = [0, 0, -6, 0]

תשובה

המטרה היא לחשב את מכפלת כל הפריטים במערך הקלט למעט האיבר במיקום הנוכחי. המשמעות היא שעבור כל פריט במערך, עלינו למצוא את מכפלת כל הפריטים האחרים.

כדי למצוא את התשובה אנו משתמשים בטכניקת המכפלה המצטברת שבה אנו מחשבים את מכפלת כל הפריטים משמאל לפריט הנוכחי ומאחסנים אותה במשתנה בשם `running_product_left`. לאחר מכן, אנו מחשבים את מכפלת כל הפריטים מימין לפריט הנוכחי ומאחסנים אותה במשתנה בשם `running_product_right`. לאחר שחישבנו את המכפלות מימין ומשמאל נכפיל את המשתנים `running_product_left` ו- `running_product_right` כדי לקבל את מכפלת כל הפריטים למעט הפריט הנוכחי. אנו חוזרים על ההליך עבור כל פריט במערך.

האיור הבא יסייע בהבנת הרעיון מאחורי הפתרון:

יישום הפתרון בקוד

def product_except_self(nums):
    # Get the length of the input list
    num_elements = len(nums)
    
    # Handle the edge case when there are less than 2 items
    if num_elements < 2:
        return []
    
    # Initialize answer list and running products
    answer = [1] * num_elements
    running_product_left = 1
    running_product_right = 1
    
    # Calculate left running products
    for idx in range(num_elements):
        answer[idx] = running_product_left
        running_product_left *= nums[idx]

    # Calculate right running products and update answer
    for idx in range(num_elements - 1, -1, -1):
        answer[idx] *= running_product_right
        running_product_right *= nums[idx]

    return answer

נבחן את הפונקציה:

# Test cases
print(product_except_self([3,2,5])) # 10, 15, 6
print(product_except_self([1,2,3,4])) # 24,12,8,6
print(product_except_self([2,2,2,2])) # 8,8,8,8
print(product_except_self([1,1,1,1])) # 1, 1, 1, 1
print(product_except_self([1,-2,0,3])) # 0, 0, -6, 0
print(product_except_self([1,3])) # 3,1
print(product_except_self([1])) # []

נסביר:

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

2. אתחול: הקוד מאתחל רשימה ריקה `answer` כדי לאחסן את התוצאות הסופיות. כמו כן, הוא מאתחל שני משתנים, `running_product_left` ו- `running_product_right`, ל-1, אשר ישמשו לאחסון המכפלות המצטברות.

3. מכפלות מצטברות משמאל: הקוד עובר בלולאה על מערך הקלט משמאל לימין. עבור כל איבר, הוא מאחסן את הערך הנוכחי של `running_product_left` במיקום המתאים ברשימת `answer` ולאחר מכן מעדכן את `running_product_left` על ידי הכפלתו באיבר הנוכחי. פעולה זו מחשבת באופן אפקטיבי את מכפלת כל האיברים משמאל לפריט הנוכחי.

4. מכפלות מצטברות מימין ועדכון התשובה: הקוד עובר בלולאה על הקלט מימין לשמאל. עבור כל איבר, הוא מכפיל את האיבר המתאים ברשימת `answer` בערך הנוכחי של `running_product_right` ולאחר מכן מעדכן את `running_product_right` על ידי הכפלתו באיבר הנוכחי. פעולה זו מחשבת באופן אפקטיבי את מכפלת כל האיברים מימין לפריט הנוכחי ומעדכנת את רשימת `answer` בהתאם.

5. לבסוף, הפונקציה מחזירה את המערך `answer`, אשר כעת מכיל את מכפלת כל האיברים במערך הקלט למעט האיבר במיקום הנוכחי.

הערכת ביצועי הפונקציה

סיבוכיות זמן:

הקוד מריץ 2 לולאות על מערך הקלט: אחד לחישוב מכפלות מצטברות משמאל לימין ואחר לחישוב מכפלות מצטברות מימין לשמאל. כל לולאה עוברת על המערך כולו פעם אחת בלבד. לכן, סיבוכיות הזמן הכוללת היא `O(N)`, כאשר N הוא אורך מערך הקלט.

סיבוכיות מקום:

הקוד מציג מערך נוסף `answer` לאחסון התוצאות הסופיות. למערך זה יש את אותו גודל כמו מערך הקלט, מה שמביא לסיבוכיות מקום של `O(N)`.

מדריכים נוספים בסדרה ללימוד פייתון שעשויים לעניין אותך

חידה תכנותית: תת מערך בעל סכום מירבי

חידה תכנותית: twoSum

רקורסיה בפייתון - כל מה שרצית לדעת ועוד כמה דברים חשובים

לכל המדריכים בסדרה ללימוד פייתון

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים