חידה תכנותית: מכפלת כל הפריטים במערך מלבד הנוכחי
כתוב פונקציה המקבלת מערך של מספרים שלמים ומחזירה מערך של מספרים שלמים שבו כל איבר הוא התוצר של מכפלת כל הפריטים במערך הקלט למעט האיבר באותו אינדקס. אל תשתמש בחילוק לצורך הפתרון.
לדוגמה:
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])) # []
נסביר:
-
טיפול בקלט: הקוד מתחיל מבדיקה האם אורך מערך הקלט קטן מ-2 פריטים. אם כן, הוא מחזיר רשימה ריקה מכיוון שאין פריטים נוספים לנוכחי.
-
אתחול: הקוד מאתחל רשימה ריקה `answer` כדי לאחסן את התוצאות הסופיות. כמו כן, הוא מאתחל שני משתנים, `running_product_left` ו- `running_product_right`, ל-1, אשר ישמשו לאחסון המכפלות המצטברות.
-
מכפלות מצטברות משמאל: הקוד עובר בלולאה על מערך הקלט משמאל לימין. עבור כל איבר, הוא מאחסן את הערך הנוכחי של `running_product_left` במיקום המתאים ברשימת `answer` ולאחר מכן מעדכן את `running_product_left` על ידי הכפלתו באיבר הנוכחי. פעולה זו מחשבת באופן אפקטיבי את מכפלת כל האיברים משמאל לפריט הנוכחי.
-
מכפלות מצטברות מימין ועדכון התשובה: הקוד עובר בלולאה על הקלט מימין לשמאל. עבור כל איבר, הוא מכפיל את האיבר המתאים ברשימת `answer` בערך הנוכחי של `running_product_right` ולאחר מכן מעדכן את `running_product_right` על ידי הכפלתו באיבר הנוכחי. פעולה זו מחשבת באופן אפקטיבי את מכפלת כל האיברים מימין לפריט הנוכחי ומעדכנת את רשימת `answer` בהתאם.
-
לבסוף, הפונקציה מחזירה את המערך `answer`, אשר כעת מכיל את מכפלת כל האיברים במערך הקלט למעט האיבר במיקום הנוכחי.
הערכת ביצועי הפונקציה
סיבוכיות זמן:
הקוד מריץ 2 לולאות על מערך הקלט: אחד לחישוב מכפלות מצטברות משמאל לימין ואחר לחישוב מכפלות מצטברות מימין לשמאל. כל לולאה עוברת על המערך כולו פעם אחת בלבד. לכן, סיבוכיות הזמן הכוללת היא `O(N)`, כאשר N הוא אורך מערך הקלט.
סיבוכיות מקום:
הקוד מציג מערך נוסף `answer` לאחסון התוצאות הסופיות. למערך זה יש את אותו גודל כמו מערך הקלט, מה שמביא לסיבוכיות מקום של `O(N)`.
מדריכים נוספים בסדרה ללימוד פייתון שעשויים לעניין אותך
חידה תכנותית: תת מערך בעל סכום מירבי
רקורסיה בפייתון - כל מה שרצית לדעת ועוד כמה דברים חשובים
לכל המדריכים בסדרה ללימוד פייתון
אהבתם? לא אהבתם? דרגו!
0 הצבעות, ממוצע 0 מתוך 5 כוכבים
המדריכים באתר עוסקים בנושאי תכנות ופיתוח אישי. הקוד שמוצג משמש להדגמה ולצרכי לימוד. התוכן והקוד המוצגים באתר נבדקו בקפידה ונמצאו תקינים. אבל ייתכן ששימוש במערכות שונות, דוגמת דפדפן או מערכת הפעלה שונה ולאור השינויים הטכנולוגיים התכופים בעולם שבו אנו חיים יגרום לתוצאות שונות מהמצופה. בכל מקרה, אין בעל האתר נושא באחריות לכל שיבוש או שימוש לא אחראי בתכנים הלימודיים באתר.
למרות האמור לעיל, ומתוך רצון טוב, אם נתקלת בקשיים ביישום הקוד באתר מפאת מה שנראה לך כשגיאה או כחוסר עקביות נא להשאיר תגובה עם פירוט הבעיה באזור התגובות בתחתית המדריכים. זה יכול לעזור למשתמשים אחרים שנתקלו באותה בעיה ואם אני רואה שהבעיה עקרונית אני עשוי לערוך התאמה במדריך או להסיר אותו כדי להימנע מהטעיית הציבור.
שימו לב! הסקריפטים במדריכים מיועדים למטרות לימוד בלבד. כשאתם עובדים על הפרויקטים שלכם אתם צריכים להשתמש בספריות וסביבות פיתוח מוכחות, מהירות ובטוחות.
המשתמש באתר צריך להיות מודע לכך שאם וכאשר הוא מפתח קוד בשביל פרויקט הוא חייב לשים לב ולהשתמש בסביבת הפיתוח המתאימה ביותר, הבטוחה ביותר, היעילה ביותר וכמובן שהוא צריך לבדוק את הקוד בהיבטים של יעילות ואבטחה. מי אמר שלהיות מפתח זו עבודה קלה ?
השימוש שלך באתר מהווה ראייה להסכמתך עם הכללים והתקנות שנוסחו בהסכם תנאי השימוש.