Find Pivot Index
ניתן לך מערך של מספרים שלמים nums. אינדקס ציר הוא אינדקס שבו סכום הערכים שמשמאלו שווה לסכום הערכים שמימינו. הערך שבאינדקס הציר עצמו אינו שייך לאף אחד מהצדדים, והסכום של צד שאין בו ערכים הוא 0.
החזר את אינדקס הציר השמאלי ביותר, או -1 אם אין אינדקס שהוא אינדקס ציר.
פונקציה
- numsinteger-array
- מערך המספרים השלמים לאיזון
- מחזירהinteger
- אינדקס הציר השמאלי ביותר, או -1 אם אין כזה
אילוצים
1 ≤ nums.length ≤ 104-1000 ≤ nums[i] ≤ 1000
דוגמאות
- קלט
- nums = [3, 1, 5, 2, 2]
- פלט
- 2
- הסבר
- באינדקס 2 הצד השמאלי הוא 3 + 1 = 4 והצד הימני הוא 2 + 2 = 4. אינדקס 0 ואינדקס 1 אינם מאוזנים (0 בצד שמאל לעומת 10, 3 בצד שמאל לעומת 9), ולכן 2 הוא נקודת הציר השמאלית ביותר.
- קלט
- nums = [1, 2, 3]
- פלט
- -1
- הסבר
- שלושת המועמדים נותנים 0 מול 5, 1 מול 3 ו־3 מול 0. אף אינדקס אינו מאזן, ולכן התשובה היא
-1.
- קלט
- nums = [4, -4, 9]
- פלט
- 2
- הסבר
- באינדקס 2, הצד השמאלי הוא 4 + (-4) = 0 והצד הימני ריק, ולכן גם הסכום שלו הוא 0. האינדקס האחרון יכול להיות נקודת הציר.
+17 בדיקות נסתרות בשליחה
שאלת המשך
האם אפשר למצוא את הציר השמאלי ביותר על ידי קריאת כל ערך פעם אחת בלבד, בלי לחשב קודם את הסכום הכולל? כמה זיכרון זה דורש?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
בדיקת אינדקס אחד דורשת שני סכומים: הערכים שלפניו והערכים שאחריו. חיבור שלהם מחדש עבור כל אינדקס חוזר כמעט על כל העבודה. איך שני הסכומים עבור האינדקס
iקשורים לאלה של האינדקסi+1?מעבר צעד אחד ימינה מוסיף את
nums[i]לסכום שמשמאל. וברגע שיודעים את הסכום של המערך כולו, אפשר להסיק את הסכום שמימין מזה שמשמאל: הוא הסכום הכולל פחות הסכום שמשמאל ופחותnums[i].תחילה חבר את כל המערך. לאחר מכן עבור משמאל לימין תוך שמירה על סכום מצטבר משמאל. בכל אינדקס, השווה את הסכום משמאל לסכום הכולל פחות הסכום משמאל פחות הערך הנוכחי; החזר את האינדקס בהתאמה הראשונה, ורק לאחר ההשוואה הוסף את הערך הנוכחי לסכום משמאל. אם הלולאה מסתיימת, החזר -1.
פתרון
בדיקת אינדקס אחד דורשת שני סכומים, אבל חישובם מחדש בכל אינדקס גורם לכמות העבודה לגדול כריבוע האורך. הפתרון הוא להפסיק לחשב אותם מחדש: הסכום משמאל גדל בערך אחד בכל צעד, והסכום מימין הוא מה שנותר מהסכום הכולל. מעבר אחד לחישוב הסכום הכולל ומעבר שני עם סכום מצטבר משמאל מוצאים את נקודת הציר השמאלית ביותר, תוך שימוש בשני מספרים בזיכרון.
חברו את שני הצדדים בכל אינדקס
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
פעלו לפי ההגדרה. עבור כל אינדקס i, סכמו את הערכים שלפניו, סכמו את הערכים שאחריו והשוו בין הסכומים. האינדקס הראשון שבו שני הסכומים שווים הוא התשובה, כי בודקים את האינדקסים משמאל לימין.
הקצוות מסתדרים מעצמם. באינדקס 0 הלולאה השמאלית רצה אפס פעמים, ולכן הסכום השמאלי הוא 0; באינדקס האחרון הלולאה הימנית רצה אפס פעמים. לכן [4, -4, 9] מחזיר 2.
העלות היא הבעיה. בכל אינדקס מסכמים את n-1 הערכים האחרים, ולכן העבודה הכוללת היא בערך n² חיבורים. עבור 10,000 ערכים מדובר בכמעט 100 מיליון חיבורים, ורובם חוזרים על סכומים שכבר חישבתם אינדקס אחד קודם.
אלגוריתם
- עבור על כל אינדקס של
numsבאמצעות לולאה עםi. - חבר את הערכים מ-
nums[0]ועדnums[i-1]כסכום השמאלי. - חבר את הערכים מ-
nums[i+1]ועד הערך האחרון כסכום הימני. - אם שני הסכומים שווים, החזר את
i. - אם אין אינדקס מתאים, החזר -1.
def pivotIndex(nums):
n = len(nums)
for i in range(n):
left = 0
for j in range(i):
left += nums[j]
right = 0
for j in range(i + 1, n):
right += nums[j]
if left == right:
return i
return -1מערך סכומים מצטברים
האינטואיציה
הגישה של כוח גס ממשיכה לסכם ריצות של המערך. מערך סכומי קידומות מבצע את העבודה הזו פעם אחת. נסמן את הסכום של k הערכים הראשונים ב-prefix[k], כאשר prefix[0] = 0. עבור [3, 1, 5, 2, 2], זהו [0, 3, 4, 9, 11, 13].
כעת, כל ריצה היא ההפרש בין שני איברים. הצד השמאלי של האינדקס i כולל את i הערכים הראשונים, ולכן הוא prefix[i]. הצד הימני כולל את כל מה שאחרי nums[i], כלומר prefix[n] - prefix[i+1]. באינדקס 2 מתקבלים 4 בצד שמאל ו-13 - 9 = 4 בצד ימין, ולכן זהו ציר.
בניית המערך דורשת מעבר אחד, וכל בדיקה דורשת זמן קבוע, ולכן החיפוש כולו הוא O(n). המחיר הוא n+1 מספרים נוספים בזיכרון.
אלגוריתם
- צרו את
prefixבאורךn+1עםprefix[0] = 0. - מלאו אותו:
prefix[k+1] = prefix[k] + nums[k]. - עבור כל אינדקס
i, קראו את הסכום משמאל בתורprefix[i]ואת הסכום מימין בתורprefix[n] - prefix[i+1]. - החזירו את
iהראשון שעבורו הם שווים, או-1לאחר הלולאה.
def pivotIndex(nums):
n = len(nums)
# prefix[k] is the sum of the first k values.
prefix = [0] * (n + 1)
for k in range(n):
prefix[k + 1] = prefix[k] + nums[k]
for i in range(n):
left = prefix[i]
right = prefix[n] - prefix[i + 1]
if left == right:
return i
return -1הסכום הכולל וסכום מצטבר משמאל
האינטואיציה
בדוק אילו איברי קידומת הגישה הקודמת קוראת. באינדקס i היא זקוקה ל־prefix[i], ל־prefix[i+1] ול־prefix[n]. האחרון הוא הסכום הכולל, שאינו משתנה לעולם, ושני האחרים הם הסכום המצטבר שהיה מתקבל אילו עברת פעם אחת על המערך. לכן אפשר לשמור את הסכום הכולל ואת הסכום המצטבר משמאל בלבד, במקום את המערך כולו.
כל ערך נמצא משמאל, בנקודת הציר או מימין. לכן הסכום מימין הוא הסכום הכולל פחות הסכום משמאל ופחות nums[i]. עבור [3, 1, 5, 2, 2] הסכום הכולל הוא 13. באינדקס 0 הסכום משמאל הוא 0 והסכום מימין הוא 13 - 0 - 3 = 10. באינדקס 1 הסכומים הם 3 לעומת 9. באינדקס 2 הסכומים הם 4 לעומת 13 - 4 - 5 = 4, ולכן מחזירים 2.
הסדר בתוך הלולאה חשוב. קודם משווים, ורק אז מוסיפים את nums[i] לסכום משמאל, כך שהסכום משמאל לעולם אינו כולל את הערך באינדקס שנבדק. החזרה בתוצאה בהתאמה הראשונה מחזירה את נקודת הציר השמאלית ביותר.
קוראים את המערך פעמיים, פעם אחת כדי לחשב את הסכום הכולל ופעם אחת כדי לסרוק אותו, ולכן זמן הריצה הוא O(n). נשמרים רק שני מספרים, ולכן המקום הנוסף הוא O(1).
אלגוריתם
- הוסף כל ערך אל
total. - הגדר את
leftל־0. - עבור כל אינדקס
i, אםleftשווה ל־total - left - nums[i], החזר אתi. - אחרת, הוסף את
nums[i]אלleftוהמשך הלאה. - אם הלולאה מסתיימת, החזר -1.
def pivotIndex(nums):
total = sum(nums)
left = 0
for i, value in enumerate(nums):
# Everything that is not on the left and not nums[i] is on the right.
if left == total - left - value:
return i
left += value
return -1
מלכודות ומקרי קצה
ברוב התשובות השגויות, הערך של הציר עצמו נכלל באחד הצדדים או שמדלגים על אינדקס בקצה.
- הוספת
nums[i]לסכום השמאלי לפני ההשוואה. הצד השמאלי כולל אז את ערך הציר, ו-[3, 1, 5, 2, 2]כבר לא מוצא את אינדקס 2. - חישוב הצד הימני בתור
total - left. כךnums[i]נכלל בצד הימני; צריך גם להפחית אותו. - דילוג על אינדקס 0 או על האינדקס האחרון. שניהם יכולים להיות הציר, כי סכום של צד ריק הוא 0.
[1, -1, 1]מחזיר 0 ו-[4, -4, 9]מחזיר 2. - החזרת ההתאמה האחרונה במקום הראשונה. ב-
[0, 0, 0]כל אינדקס מאזן את הסכומים, והתשובה היא 0. - שימוש בשני מצביעים שמתקדמים פנימה משני הקצוות ומגדילים את הצד הקטן יותר. זה עובד רק כאשר כל הערכים אינם שליליים; כאן הערכים יורדים עד -1000, ולכן סכום של צד יכול לקטון תוך כדי הגדילה שלו.
- שכחה שהמערכים ב-Lua וב-R מתחילים ב-1. יש להחזיר
i-1כדי שהתשובה תהיה אינדקס שמתחיל מ-0.
שאלות נפוצות4
מהי סיבוכיות הזמן של Find Pivot Index?
פתרון הסכום הכולל והסכום המצטבר רץ בזמן O(n): מעבר אחד כדי לחבר את איברי המערך ומעבר אחד כדי לסרוק אותו. הוא משתמש במקום נוסף של O(1). חישוב מחדש של שני הצדדים בכל אינדקס דורש במקום זאת זמן O(n²).
למה הסכום הימני שווה לסך הכול פחות השמאלי פחות nums[i]?
כל ערך במערך נמצא בדיוק באחד משלושה מקומות: משמאל ל־i, ב־i או מימין ל־i. הסכומים שלהם מסתכמים בסכום הכולל, ולכן הסכום מימין הוא הסכום הכולל פחות שני החלקים האחרים. כך אפשר לבדוק אינדקס בלי לחשב את הסכום של הצד הימני.
האם אפשר לפתור את Find Pivot Index באמצעות שני מצביעים?
לא באופן אמין. סריקה בעזרת שני מצביעים שתמיד מרחיבה את הצד הקטן יותר מניחה שהוספת ערך מגדילה צד, אך ההנחה הזאת נכשלת ברגע שערכים יכולים להיות שליליים: צד יכול להתכווץ בזמן שמרחיבים אותו, ולכן הסריקה עלולה להזיז מצביע מעבר לנקודת הציר האמיתית. שיטת הסכום המצטבר אינה מניחה דבר לגבי סימני הערכים ובודקת כל אינדקס.
מהו אינדקס הציר של מערך בעל איבר אחד?
התוצאה היא 0. שני הצדדים של האיבר היחיד ריקים, וסכום של צד ריק הוא 0, ולכן שני הצדדים שווים. הפתרון באמצעות סכום מצטבר מחזיר 0 בהשוואה הראשונה: הצד השמאלי הוא 0, וגם הסכום הכולל פחות 0 ופחות הערך הוא 0.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def pivotIndex(nums):
# כתבו כאן קודמקרה 1
מקרה 2
מקרה 3
קלט
nums = [3, 1, 5, 2, 2]
צפוי
2