Longest Consecutive Sequence
נתון לך מערך של מספרים שלמים nums בסדר שרירותי. רצף עוקב הוא קבוצת ערכים x, x+1, x+2 וכן הלאה, שכל אחד מהם מופיע במקום כלשהו ב-nums. החזר את האורך של הרצף העוקב הארוך ביותר. ערך שמופיע יותר מפעם אחת נספר פעם אחת.
פונקציה
- numsinteger-array
- המספרים השלמים, בכל סדר, אפשר לחזור עליהם
- מחזירהinteger
- אורך הרצף הארוך ביותר של ערכים עוקבים שנמצאים ב־nums
אילוצים
1 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109- ערכים עשויים לחזור. המיקומים במערך אינם חשובים, רק אילו ערכים קיימים.
דוגמאות
- קלט
- nums = [40, 4, 39, 1, 3, 2, 41]
- פלט
- 4
- הסבר
1,2,3ו־4נמצאים כולם, רצף של 4, אף שהם מפוזרים לאורך המערך. ברצף השני, מ־39עד41, יש רק 3 ערכים.
- קלט
- nums = [7, 3, 7, 5, 6, 5]
- פלט
- 3
- הסבר
5,6ו־7יוצרים רצף באורך 3. ה־7השני וה־5השני אינם מוסיפים דבר, ו־3לא יכול להצטרף כי4חסר.
- קלט
- nums = [10, 30, 20]
- פלט
- 1
- הסבר
- אין שני ערכים שההפרש ביניהם הוא 1, ולכן כל רצף מכיל ערך יחיד והתשובה היא 1.
שאלת המשך
נניח שהערכים מגיעים בזה אחר זה, ואחרי כל ערך עליך לדווח על הרצף הארוך ביותר עד כה. האם תוכל לעדכן את התשובה בזמן ממוצע של O(1) לכל ערך?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
נסה כל ערך כמספר הראשון ברצף וספור כלפי מעלה. איזו שאלה אתה שואל שוב ושוב, ומה עולה כל תשובה כשאתה מחפש אותה במערך?
השאלה היא "האם
x+1נמצא במערך?". קבוצת גיבוב עונה עליה בזמן קבוע בממוצע, והיא גם מסירה את הכפילויות.התחל לספור רק בערך
xשעבורוx-1חסר בקבוצה. משם, התקדם אלx+1,x+2וכן הלאה כל עוד הקבוצה מכילה אותם, ושמור את המסלול הארוך ביותר. כל ערך נכלל אפוא במסלול אחד בלבד.
פתרון
ערכי ריצה יכולים להימצא בכל מקום במערך. מיון מסדר אותם בזמן O(n log n). קבוצת גיבוב בודקת אם x+1 נמצא כאן בזמן O(1), ואם סופרים רק מערכים שבהם x-1 חסר, עוברים על כל ערך פעם אחת: O(n) בסך הכול.
סופרים כלפי מעלה מכל ערך על ידי חיפוש במערך
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
התייחס לכל ערך כאל התחלה אפשרית של רצף. החל מ־x, חפש במערך את x+1, ואז את x+2, עד שחסר ערך, ושמור את האורך הגדול ביותר. לכל רצף יש ערך קטן ביותר בתוך nums, והלולאה עוברת על כל הרצף החל ממנו.
כל חיפוש קורא עד n ערכים, ועל רצף ארוך עוברים שוב מכל אחד מהאיברים שלו. עבור 10^4 ערכים שיוצרים רצף אחד בסדר מעורבב, המעברים אורכים בערך n²/2 = 5 × 10^7 צעדים, כשבכל סריקה עוברים בממוצע על חצי מהמערך: כ־2.5 × 10^11 השוואות.
אלגוריתם
- הגדר את
bestל־0. - עבור כל ערך
startב־nums, הגדר אתcurrentל־startואתlengthל־1. - כל עוד סריקה של
numsמוצאת אתcurrent+1, הוסף 1 ל־currentול־length. - שמור את
lengthב־bestאם הוא גדול יותר. - החזר את
best.
def longestConsecutive(nums):
best = 0
for start in nums:
current = start
length = 1
# "in" on a list reads it from the front until it finds the value.
while current + 1 in nums:
current += 1
length += 1
best = max(best, length)
return bestמיין ואז ספור רצפים
האינטואיציה
המיון מציב את הערכים של כל רצף זה לצד זה: [40, 4, 39, 1, 3, 2, 41] הופך ל־[1, 2, 3, 4, 39, 40, 41], ואת הרצפים קוראים משמאל לימין.
עוברים על הערכים הממוינים ושומרים את האורך של הרצף הנוכחי. ערך שגדול באחד מהערך הקודם מאריך אותו. ערך שחוזר על עצמו אינו מאריך את הרצף וגם אינו מסיים אותו, ולכן מדלגים עליו. כל ערך אחר מתחיל רצף חדש באורך 1.
המיון עולה O(n log n) והמעבר עולה O(n). מיון במקום אינו דורש מערך נוסף; שפות שממיינות עותק משתמשות בזיכרון O(n).
אלגוריתם
- מיינו את
numsבסדר עולה. - הגדירו את
bestואתrunל־1, מכיוון שהמערך לעולם אינו ריק. - עבור כל אינדקס
iהחל מ־1, דלגו עלnums[i]אם הוא שווה ל־nums[i-1]. - אם
nums[i]הואnums[i-1]+1, הוסיפו 1 ל־run; אחרת הגדירו אתrunל־1. שמרו אתrunב־bestאם הוא גדול יותר. - החזירו את
best.
def longestConsecutive(nums):
nums.sort()
best = 1
run = 1
for i in range(1, len(nums)):
if nums[i] == nums[i - 1]:
continue # a repeat neither extends nor breaks the run
if nums[i] == nums[i - 1] + 1:
run += 1
else:
run = 1
best = max(best, run)
return bestקבוצת גיבוב, ספירה רק מתחילת כל ריצה
האינטואיציה
עבור כל ערך בקבוצת גיבוב, בדיקת חברות עולה בממוצע O(1), וערכים חוזרים מתאחדים לרשומה אחת.
מעבר מכל ערך עדיין היה גורם לחזרה על עבודה: ברצף 1, 2, 3, 4 היית מבצע 3 צעדים מ־1, 2 מ־2 ו־1 מ־3. לכן יש להתחיל מעבר רק מהערך הראשון ברצף, שהוא בדיוק ערך x שעבורו x-1 חסר. בדוגמה 1 רק 1 ו־39 מתאימים, והם יוצרים רצפים באורך 4 ו־3.
כל ערך שייך לרצף אחד, והמעבר של אותו רצף בלבד עובר עליו, ולכן כל המעברים יחד אורכים לכל היותר n צעדים. עם בדיקה אחת לכל ערך, הסיבוכיות הכוללת היא O(n) בזמן ו־O(n) בזיכרון עבור הקבוצה.
אלגוריתם
- הכניסו כל ערך של
numsלקבוצת גיבובvalues, והגדירו אתbestל־0. - עבור כל ערך
xבקבוצה, דלגו עליו אםx-1נמצא בקבוצה: הוא אינו הערך הראשון ברצף שלו. - אחרת, הגדירו את
endל־xוהגדילו אותו ב־1 כל עודend+1נמצא בקבוצה. - שמרו את
end-x+1ב־bestאם הוא גדול יותר. - החזירו את
best.
def longestConsecutive(nums):
values = set(nums)
best = 0
for value in values:
# Only a value with no left neighbour starts a run.
if value - 1 in values:
continue
end = value
while end + 1 in values:
end += 1
best = max(best, end - value + 1)
return best
מלכודות ומקרי קצה
- התייחסות לערך חוזר כאל פער או כאל צעד אחרי המיון. ב־
[1, 2, 2, 3], איפוס הרצף ב־2השני נותן 2, וספירתו כצעד נותנת 4. התשובה היא 3. - התחלת
bestב־0 במעבר על הערכים הממוינים ועדכונו רק בתוך הלולאה. מערך עם ערך אחד מחזיר אז 0 במקום 1. - מעבר על כל ערך בקבוצה במקום רק על תחילות של רצפים. מעבר על רצף אחד של
10^4ערכים עולה אז5 × 10^7צעדים. - מעבר בלולאה על
numsבמקום על הקבוצה. אם הערך הראשון ברצף שאורכו 2,500 מופיע 2,000 פעמים, עוברים על הרצף 2,000 פעמים. - שימוש בערכים כאינדקסים של מערך. הערכים מגיעים עד
±10^9, ולכן נדרשות2 × 10^9רשומות.
שאלות נפוצות3
מהי סיבוכיות הזמן של רצף האיברים העוקבים הארוך ביותר?
פתרון קבוצת הגיבוב פועל בזמן ממוצע של O(n) ודורש זיכרון נוסף של O(n). מיון וספירת הרצפים אורכים O(n log n). חיפוש במערך אחר כל ערך הבא ללא קבוצה עשוי לארוך עד O(n³).
האם תוכל לפתור את בעיית הרצף הרציף הארוך ביותר בלי זיכרון נוסף?
כן, אם מותר לך לסדר מחדש את הקלט: מיין אותו במקום וספור רצפים במעבר אחד, תוך דילוג על חזרות. כך נדרשת זיכרון נוסף של O(1), אבל זמן של O(n log n). הפתרון ב־O(n) דורש קבוצת גיבוב.
האם union-find יכול לפתור את בעיית הרצף הארוך ביותר של מספרים עוקבים?
כן. הפוך כל ערך ייחודי לקבוצה, חבר את x עם x+1 בכל פעם ששניהם קיימים, והחזר את גודלה של הקבוצה הגדולה ביותר. זמן הריצה קרוב ל־O(n), אך נדרשת מפה של ערכים לאינדקסים, קישורי הורה וגדלים, בעוד שמעבר על קבוצת הגיבוב דורש קבוצה אחת.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def longestConsecutive(nums):
# כתבו כאן את הקודבדיקה #1
בדיקה #2
בדיקה #3
ארגומנט
nums = [40, 4, 39, 1, 3, 2, 41]
הפלט הצפוי
4