Find the Duplicate Number
מקבלים מערך nums של n+1 מספרים שלמים, שכל אחד מהם בין 1 ל-n. ערך אחד בדיוק מופיע יותר מפעם אחת, אולי פעמים רבות, ועליך להחזיר את הערך הזה.
פתור זאת בלי לשנות את nums ועם כמות קבועה בלבד של זיכרון נוסף.
פונקציה
- numsinteger-array
- n+1 מספרים שלמים, כל אחד בין 1 ל־n
- מחזירהinteger
- הערך שמופיע יותר מפעם אחת
אילוצים
1 ≤ n ≤ 104nums.length == n+11 ≤ nums[i] ≤ n- ערך אחד מופיע פעמיים או יותר; כל ערך אחר מופיע לכל היותר פעם אחת.
דוגמאות
- קלט
- nums = [2, 5, 1, 3, 5, 4]
- פלט
- 5
- הסבר
- כאן
nהוא 5, ו-5 מופיע במיקומים 1 ו-4, לכן התשובה היא 5. כל ערך אחר מ-1 עד 5 מופיע פעם אחת.
- קלט
- nums = [4, 2, 4, 1, 4]
- פלט
- 4
- הסבר
- 4 מופיע שלוש פעמים, במיקומים 0, 2 ו-4, ואילו 3 אינו מופיע כלל. ערך שחוזר על עצמו יכול להחליף כמה ערכים חסרים, ולכן התשובה היא 4.
+17 בדיקות נסתרות בשליחה
שאלת המשך
החיפוש הבינארי בערכים שומר על שתי הכללים בזמן O(n log n). האם תוכל לשמור עליהם בזמן O(n)?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
כל ערך נמצא בין 1 ל־
n, ולמערך יש מיקומים מ־0 עדn. לכן כל ערך הוא גם מיקום תקף. מתחילים במיקום 0, קופצים למיקוםnums[0], ואז למיקום שמציין הערך הזה, וכך הלאה. מה חייב לקרות בהליכה הזאת?ההליכה לעולם אינה נעצרת ויש לה רק
n+1מיקומים לבקר בהם, ולכן היא נכנסת ללולאה. מגיעים למיקום שבו היא נכנסת ללולאה משני מיקומים שונים, ושניהם מחזיקים את המיקום הזה כערך שלהם.מצאו את הכניסה ללולאה באמצעות שני מצביעים שמתחילים במיקום 0: אחד קופץ פעם אחת בכל סיבוב, והאחר קופץ פעמיים, עד שהם נוחתים באותו מיקום. לאחר מכן החזירו אחד מהם ל-0 והזיזו את שניהם בקפיצה אחת בכל פעם. הם נפגשים בכניסה, וזו התשובה.
פתרון
קבוצת גיבוב או מיון מוצאים מיד את הערך החוזר, אבל שניהם מפרים את הכללים: קבוצת הגיבוב זקוקה לזיכרון עבור כל ערך, ומיון משנה את nums. הפתרון נמצא במספרים. כל ערך הוא בין 1 ל-n, ולכן הוא גם מיקום תקף במערך. קראו כל ערך כקישור למיקום אחר, ובעקבות הקישורים ממיקום 0 מגיעים תמיד ללולאה שהכניסה אליה היא הערך הכפול. המצביעים המהירים והאיטיים של Floyd מוצאים את הכניסה הזו בעזרת שני מספרים שלמים.
השוו בין כל זוג
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
הערך החוזר מופיע לפחות בשני מקומות i < j. השווה כל מקום לכל מקום שאחריו; הזוג הראשון שבו הערכים שווים נותן את התשובה. בדוגמה הראשונה, במקום 1 מופיע 5, והסריקה החל ממקום 2 ואילך מוצאת 5 נוסף במקום 4.
כך נשמרים שני הכללים: לא נכתב דבר, והזיכרון היחיד הוא שני מוני לולאה. זה איטי כי הוא משווה בין זוגות. עם n+1 = 10,001 ערכים, כששני העותקים נמצאים סמוך לסוף, הוא בודק כ-5 × 10^7 זוגות.
אלגוריתם
- עבור כל מיקום
iמ־0 ועד הסוף: - עבור כל מיקום
jשאחריi, השווה אתnums[i]ל־nums[j]. - החזר את
nums[i]בהתאמה הראשונה.
def findDuplicate(nums):
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] == nums[j]:
return nums[i]
return -1 # unreachable: the input always holds a repeatחיפוש בינארי לפי ערך
האינטואיציה
חפש בטווח הערכים, לא במיקומים. בחר ערך סף m וספור כמה איברים ב־nums קטנים או שווים ל־m.
אם הערך הכפול d גדול מ־m, כל אחד מהערכים 1 עד m מופיע לכל היותר פעם אחת, ולכן הספירה היא לכל היותר m. אם d קטן או שווה ל־m, כל ערך שגדול מ־m מופיע לכל היותר פעם אחת, ולכן לכל היותר n-m איברים גדולים מ־m, ולפחות m+1 איברים קטנים או שווים ל־m. לכן הבדיקה "count > m" מחזירה false לכל m שקטן מ־d, ו־true החל מ־d. חיפוש בינארי מוצא את m הראשון שבו התוצאה הופכת ל־true, וזהו d.
בדוגמה השנייה, n הוא 4. עבור m = 2, האיברים 2 ו־1 נותנים ספירה של 2, שאינה גדולה מ־2, לכן התשובה גדולה מ־2. עבור m = 3, הספירה עדיין 2, לכן התשובה היא 4. בכל סבב קוראים את המערך כולו פעם אחת ומחלקים את הטווח לחצי, לכן זמן הריצה הוא O(n log n): כ־14 מעברים על 10,001 ערכים.
אלגוריתם
- קבעו את
low= 1 ואתhigh=n, אורךnumsפחות אחד. - כל עוד
low < high, קחו אתmidשנמצא באמצע ביניהם. - ספרו את האיברים ב־
numsשקטנים או שווים ל־mid. - אם הספירה גדולה מ־
mid, קבעו אתhigh=mid; אחרת קבעו אתlow=mid+1. - החזירו את
low.
def findDuplicate(nums):
low, high = 1, len(nums) - 1
while low < high:
mid = (low + high) // 2
# How many values fall in 1..mid?
count = 0
for x in nums:
if x <= mid:
count += 1
if count > mid:
high = mid # 1..mid holds more values than it has room for
else:
low = mid + 1 # the repeat is above mid
return lowזיהוי מחזור של פלויד בקישורי הערכים
האינטואיציה
קראו את המערך כאילו הוא אוסף של קישורים: המיקום i מצביע למיקום nums[i]. לכל מיקום מ-0 עד n יש קישור יוצא אחד בדיוק, וכל קישור מגיע למיקום כלשהו בטווח 1 עד n. בדוגמה הראשונה הקישורים הם 0 → 2, 1 → 5, 2 → 1, 3 → 3, 4 → 5 ו-5 → 4.
התחילו במיקום 0 ועקבו אחר הקישורים. המסלול לא יכול להיעצר, כי לכל מיקום יש קישור, ויש רק n+1 מיקומים, ולכן הוא חייב לחזור למיקום שכבר ביקר בו. מכאן ואילך הוא ימשיך להסתובב לנצח. המסלול מורכב מזנב ואחריו לולאה, וצורתו כצורת האות ρ. בדוגמה הראשונה המסלול הוא 0, 2, 1, 5, 4, 5, 4 וכן הלאה: הזנב הוא 0, 2, 1 והלולאה היא 5, 4. מיקום 3 מצביע לעצמו, אבל המסלול אף פעם לא מגיע אליו, וזה לא מפריע.
הכניסה ללולאה היא הערך הכפול. המסלול נכנס ל-5 פעמיים ממיקומים שונים: פעם אחת מסוף הזנב (מיקום 1, כי nums[1] הוא 5) ופעם אחת מסוף הלולאה (מיקום 4, כי nums[4] הוא 5). שני מיקומים שונים מכילים את הערך 5, ולכן 5 מופיע שוב. הזנב תמיד מכיל את מיקום 0, כי אין ערך 0 ושום דבר אף פעם לא מצביע אליו בחזרה, ולכן לכניסה תמיד יש שתי דרכים שונות להגיע אליה. ערך אחד בדיוק מופיע שוב, ולכן הכניסה היא אותו ערך.
כעת מצאו את הכניסה באמצעות שני מצביעים, כמו בזיהוי מעגל ברשימה מקושרת. בשלב 1, slow עוקב אחר קישור אחד בכל סבב ו-fast עוקב אחר שניים, עד שהם נמצאים באותו מיקום כלשהו בלולאה. בדוגמה הראשונה הם נפגשים במיקום 4. בשלב 2, החזירו את slow ל-0, השאירו את fast במקומו, והזיזו את שניהם קישור אחד בכל סבב. הם ייפגשו בכניסה.
למה שלב 2 עובד: נניח שהזנב דורש T קישורים כדי להגיע לכניסה, ובלולאה יש C מיקומים. כשהמצביעים נפגשו, slow התקדם s צעדים ו-fast התקדם 2s צעדים. שניהם עמדו באותו מקום, ולכן s הצעדים הנוספים של fast היו מספר שלם של הקפות בלולאה. אחרי T צעדים נוספים, slow מגיע לכניסה מ-0, ו-fast עומד במקום שבו היה עומד מסלול שמתחיל ב-0 אחרי s+T צעדים, כי ההקפות הנוספות שלו לא משנות דבר. זה T צעדים עד לכניסה ועוד s צעדים, שהם מספר שלם של הקפות, ולכן גם הוא מגיע לכניסה. הם לא יכולים להיפגש מוקדם יותר, כי slow עדיין בזנב ו-fast אף פעם לא יוצא מהלולאה. בדוגמה הראשונה slow עובר דרך 2, 1, 5, ואילו fast עובר דרך 5, 4, 5, והם נפגשים ב-5 אחרי T = 3 צעדים.
כל שלב דורש O(n) צעדים, הזיכרון היחיד הדרוש הוא לשני מיקומים, ואת nums אף פעם לא משנים.
אלגוריתם
- התייחסו לכל מיקום
iכאל צומת שמקשר למיקוםnums[i], והתחילו עם שני המצביעים במיקום 0. - שלב 1: הזיזו את
slowאלnums[slow]ואתfastאלnums[nums[fast]]עד שהם יהיו שווים. - שלב 2: החזירו את
slowלמיקום 0. - הזיזו את שניהם קישור אחד בכל פעם: את
slowאלnums[slow]ואתfastאלnums[fast], עד שהם יהיו שווים. - החזירו את המיקום הזה: זהו הערך שחוזר על עצמו.
def findDuplicate(nums):
# Treat each index i as a node with one link, to nums[i].
# Phase 1: slow moves one link, fast moves two, until they meet in the cycle.
slow = fast = 0
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
# Phase 2: restart one pointer at index 0 and move both one link at a time.
# They meet at the cycle's entrance, the index two positions link to.
slow = 0
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow
מלכודות ומקרי קצה
רוב התשובות השגויות נובעות מבלבול בין מיקומים לערכים, או מעצירה של שיטת Floyd שלב אחד מוקדם מדי.
- החזרת נקודת המפגש של שלב 1. היא מיקום כלשהו בלולאה, ולא בהכרח הכניסה אליה. בדוגמה הראשונה המצביעים נפגשים ב־4, אבל התשובה היא 5.
- בדיקת
slow == fastלפני הצעד הראשון. שניהם מתחילים ב־0, ולכן הלולאה מסתיימת מיד. קודם מבצעים צעד ואז משווים, או מתחילים אותם בהפרש של חוליה אחת או שתיים. - התחלת ההליכה בכל מיקום שאינו 0. שום חוליה אינה מצביעה למיקום 0, מכיוון שאין ערך שהוא 0, וזה מה שמבטיח זנב. התחלה במיקום אחר עלולה להציב אותך בלולאה שאין דרך להיכנס אליה מבחוץ, כמו במיקום 3 בדוגמה הראשונה, שהכניסה אליו לא מוכיחה דבר.
- הנחה שהערך הכפול מופיע בדיוק פעמיים. טריק הסכום, הסכום הכולל פחות
1 + 2 + ... + n, נותן 15 פחות 10, כלומר 5, בדוגמה השנייה, אבל התשובה היא 4. כך גם לגבי טריקים המבוססים על XOR. - חיפוש בינארי על מיקומים במקום על ערכים, או בדיקת
count >= mid. מספר הערכים שקטנים או שווים ל־mהוא בדיוקmכאשר אף ערך בין 1 ל־mאינו חוזר ואף ערך אינו חסר, ולכן רק>מפריד בין שני הצדדים. - סימון ערכים שביקרת בהם באמצעות היפוך הסימן של
nums[x]או החלפת ערכים למקומם. שתי השיטות עובדות, אבל שתיהן משנות את המערך, והמשימה אוסרת זאת.
שאלות נפוצות4
מהי סיבוכיות הזמן של מציאת המספר הכפול?
זיהוי המחזור של Floyd פועל בזמן O(n) עם זיכרון נוסף של O(1): כל אחד משני השלבים שלו עוקב לכל היותר אחר כמה כפולות של n קישורים. החיפוש הבינארי בערכים אורך זמן O(n log n) וצורך זיכרון של O(1). השוואת כל זוג היא O(n²).
למה זיהוי מחזורים של Floyd מוצא את המספר הכפול?
אם קוראים כל ערך כקישור מהמיקום שלו אל המיקום שהוא מציין, ההליכה מהמיקום 0 חייבת להסתיים בלולאה, כי היא לעולם לא נעצרת ויש לה רק n+1 מקומות שאליהם היא יכולה להגיע. מגיעים למיקום שבו היא נכנסת ללולאה משני מיקומים שונים, אחד בזנב ואחד בלולאה, ולכן שתי כניסות מכילות את אותו ערך. השיטה של פלויד מוצאת את הכניסה ללולאה בעזרת שני מצביעים, ולכן היא מוצאת את הערך החוזר.
למה לא להשתמש בקבוצת גיבוב או למיין את המערך?
שניהם מוצאים את התשובה בזמן O(n) או O(n log n), ובתוכנית אמיתית כל אחת מהדרכים תהיה בסדר. המשימה אוסרת עליהן בכוונה: קבוצת גיבוב משתמשת בזיכרון נוסף של O(n), ומיון משנה את nums או מחייב ליצור עותק מלא. המגבלות הן שדוחפות אותך לעבר נקודת המבט של מעגלים.
למה נוסחת הסכום לא עובדת עבור מציאת המספר הכפול?
חיסור 1 + 2 + ... + n מסכום המערך נותן את הערך הכפול רק כשהוא מופיע בדיוק פעמיים וכל ערך אחר מופיע פעם אחת. כאן הערך החוזר יכול להופיע פעמים רבות ולבוא במקום ערכים חסרים. ב-[4, 2, 4, 1, 4] ההפרש הוא 15 פחות 10 = 5, שאפילו לא נמצא במערך.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def findDuplicate(nums):
# כתבו כאן קודמקרה 1
מקרה 2
קלט
nums = [2, 5, 1, 3, 5, 4]
צפוי
5