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.
+17 בדיקות נסתרות בשליחה
שאלת המשך
נניח שהערכים מגיעים בזה אחר זה, ואחרי כל ערך עליך לדווח על הרצף הארוך ביותר עד כה. האם תוכל לעדכן את התשובה בזמן ממוצע של 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, והמשיכו כך עד שערך חסר. מספר הערכים שהגעתם אליהם הוא הרצף שמתחיל ב־x, והגדול מבין האורכים האלה הוא התשובה.
הפתרון נכון כי לכל רצף יש ערך קטן ביותר, הערך הזה נמצא ב־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 עד 4, ואז קפיצה ל־39.
עוברים על הערכים הממוינים ושומרים את אורך הרצף הנוכחי. ערך הגדול באחד מהערך הקודם מאריך אותו. ערך השווה לערך הקודם הוא ערך שחוזר: מדלגים עליו, כי הוא לא מאריך את הרצף ולא מסיים אותו. כל ערך אחר יוצר פער, ומתחיל שם רצף חדש באורך 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קבוצת גיבוב, ספירה רק מתחילת כל ריצה
האינטואיציה
הכניסו כל ערך לקבוצת גיבוב. עכשיו הבדיקה „האם x+1 קיים?” עולה O(1) בממוצע במקום סריקה, וערכים חוזרים מתמזגים לרשומה אחת.
מעבר מכל ערך עדיין יחזור על עבודה: ברצף 1, 2, 3, 4 תבצעו 3 צעדים מ־1, 2 מ־2 ו־1 מ־3. לכן התחילו מעבר רק מהערך הראשון ברצף. ערך x הוא הראשון בדיוק כאשר x-1 אינו בקבוצה. ב־[40, 4, 39, 1, 3, 2, 41] רק 1 ו־39 עומדים בתנאי: מ־1 מגיעים ל־4, באורך 4, ומ־39 מגיעים ל־41, באורך 3.
כל ערך שייך לרצף אחד בדיוק, ורק המעבר מהערך הראשון באותו רצף עובר עליו, ולכן כל המעברים יחד דורשים לכל היותר n צעדים. הוסיפו בדיקת חברות אחת לכל ערך ואת בניית הקבוצה, והעלות הכוללת היא O(n) זמן ו־O(n) זיכרון עבור הקבוצה.
עברו על הקבוצה, לא על nums. אם הערך הראשון ברצף של 2,500 ערכים מופיע 2,000 פעמים ב־nums, מעבר על nums יוביל למעבר על אותו רצף 2,000 פעמים.
אלגוריתם
- הכניסו כל ערך של
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במקום על הקבוצה כשיש ערכים חוזרים. על הרצף שמתחיל בערך שמופיע אלפי פעמים עוברים אלפי פעמים. - סימון ערכים במערך שהאינדקסים שלו הם הערכים עצמם. הערכים מגיעים עד
±10^9, לכן המערך יצטרך להכיל2 × 10^9איברים.
שאלות נפוצות4
מהי סיבוכיות הזמן של הרצף העוקב הארוך ביותר?
פתרון קבוצת הגיבוב רץ בזמן ממוצע של O(n) ומשתמש בזיכרון נוסף של O(n). מיון ואז ספירת הרצפים דורשים זמן של O(n log n). חיפוש במערך אחר כל ערך הבא ללא קבוצה עשוי לדרוש עד O(n³).
למה הפתרון עם קבוצת גיבוב הוא O(n), כשיש בו לולאת while בתוך לולאת for?
הלולאה הפנימית רצה רק מערך שהשכן שמשמאלו x-1 חסר, כלומר הערך הראשון ברצף שלו. המעבר עובר על כל ערך במסגרת הרצף שלו בלבד, ולא במסגרת מעבר אחר, כך שכל הלולאות הפנימיות יחד מבצעות לכל היותר n צעדים. הלולאה החיצונית מוסיפה בדיקה אחת לכל ערך, כך שמתקבל O(n) בסך הכול.
האם תוכל לפתור את בעיית הרצף העוקב הארוך ביותר בלי זיכרון נוסף?
כן, אם מותר לך לשנות את סדר הקלט: מיין אותו במקום וספור רצפים במעבר אחד, תוך דילוג על חזרות. כך משתמשים בזיכרון נוסף של O(1), אבל זמן הריצה הוא O(n log n). הפתרון ב־O(n) דורש קבוצת גיבוב.
האם מבנה Union-Find יכול לפתור את בעיית הרצף הרציף הארוך ביותר?
כן. הפכו כל ערך ייחודי לקבוצה, אחדו את x עם x+1 בכל פעם ששניהם קיימים, והחזירו את גודל הקבוצה הגדולה ביותר. זמן הריצה קרוב ל־O(n), אבל הוא דורש מיפוי מערכים לאינדקסים, קישורים להורים וגדלים, בעוד שהמעבר על קבוצת הגיבוב עושה את אותה העבודה בעזרת קבוצה אחת ושתי לולאות.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def longestConsecutive(nums):
# כתבו את הקוד כאןמקרה 1
מקרה 2
מקרה 3
קלט
nums = [40, 4, 39, 1, 3, 2, 41]
צפוי
4