אתגר תכנותי: מכפלת הכל לבד מהנוכחי

יש לכתוב פונקציה `product_except_self` שתקבל קלט מערך מספרים באורך n כאשר תפקידה של הפונקציה הינו לייצר מהמערך המקורי מערך מספרים גם כן באורך n כאשר כל פריט שמיקומו i במערך הפלט הינו מכפלה של כל המספרים במערך המקורי לבד מהמספר במיקום i.

בהינתן הקלט:

Input = [1, 2, 3, 4]

צפוי הפלט:

Output = [24, 12, 8, 6]

בהינתן הקלט:

Input = [1, 0, 3, 4]

צפוי הפלט:

Output = [0, 12, 0, 0]

בהינתן הקלט:

Input = [-1, 2, -3, 4]

צפוי הפלט:

Output = [12, -24, -8, 6]

מגבלה: אסור להשתמש בחילוק.

פתרון מוצע

from typing import List
def product_except_self(nums: List[int]) -> List[int]:
    len_nums = len(nums)
   
    # Initialize the output list with 1s, to store the mediary products
    output = [1]*len_nums
   
    # Calculate and store the products when going Left-To-Right
    ltr_product = 1
    for idx in range(len_nums):
        output[idx] = ltr_product
        ltr_product *= nums[idx]
   
    # Calculate products and multiply with the existing products when going Right-To-Left
    rtl_product = 1
    for idx in range(len_nums-1, -1, -1):
        output[idx] *= rtl_product
        rtl_product *= nums[idx]
   
    return output




test_cases = [
    [],
    [1, 2],
    [1, 2, 3],
    [1, 2, 3, 4],
    [1, 0, 3, 4],
    [-1, 2, -3, 4]
]
for case in test_cases:
    print(f"{case} -> {product_except_self(case)}")

הרעיון בפתרון הוא:

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

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

הפתרון בנוי על שני שלבים עיקריים:

1. חישוב המכפלות משמאל ומימין:
• אנו מתחילים בלולאה הראשונה שמחשבת את המכפלות מימין לשמאל (Left-To-Right) ומעדכנת את מערך הפלט בהתאם.
• לאחר מכן, אנו מבצעים לולאה נוספת שמחשבת את המכפלות משמאל לימין (Right-To-Left) ומכפילה את התוצאה במערך הפלט שנוצר עד כה.
2. עדכון מערך הפלט:
• המשתנה `ltr_product` מתעדכן בכל איטרציה בלולאה הראשונה כדי לשמור את המכפלה של כל הערכים מההתחלה עד הנוכחי (משמאל לימין).
• המשתנה `rtl_product` מתעדכן בכל איטרציה בלולאה השנייה כדי לשמור את המכפלה של כל הערכים מהסוף עד הנוכחי (משמאל לימין).

הערכת יעילות הפתרון

משך הביצוע (Time Complexity):

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

זיכרון (Space Complexity):

הפתרון אינו מצריך שימוש בזיכרון נוסף מעבר למערך הפלט `output`, ולכן סיבוכיות הזיכרון היא O(1).

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

אתגר תכנותי: איסוף ערכי המקסימום בתוך חלון הזזה Sliding window maxima

טכניקת חלון ההזזה sliding window לפתרון בעיות ברצפים

פתרון בעיות אופטימיזיציה באמצעות אלגוריתם חמדן

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

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

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