Contains Duplicate
נתון לך מערך של מספרים שלמים nums. החזר true אם ערך כלשהו מופיע בו לפחות פעמיים, ו-false אם כל הערכים שונים.
פונקציה
- numsinteger-array
- המספרים השלמים לבדיקה
- מחזירהboolean
- true אם ערך כלשהו מופיע לפחות פעמיים, false אחרת
אילוצים
1 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109
דוגמאות
- קלט
- nums = [3, 1, 4, 1, 5]
- פלט
- true
- הסבר
- הערך
1מופיע באינדקס 1 ושוב באינדקס 3, לכן התשובה היאtrue.
- קלט
- nums = [2, 7, 1, 8]
- פלט
- false
- הסבר
2,7,1ו־8הם ארבעה ערכים שונים, לכן שום דבר לא חוזר על עצמו.
- קלט
- nums = [-4, 4, 0]
- פלט
- false
- הסבר
- ל־
-4ול־4יש אותו ערך מוחלט, אבל הם מספרים שונים, ו־0מופיע פעם אחת, ולכן התשובה היאfalse.
שאלת המשך
אפשר לעצור ברגע שמגיעים לערך הראשון שחוזר, במקום לקרוא תמיד את המערך כולו?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
השוואה של כל ערך עם כל ערך אחר עובדת, אבל עבור
10^4ערכים מדובר בכ־5 × 10^7השוואות. מה תוכלו לזכור על הערכים שכבר עברתם על פניהם?חזרה פירושה שהערך הנוכחי הוא ערך שכבר נתקלת בו בעבר. קבוצת גיבוב עונה על השאלה "האם נתקלתי בערך הזה?" בזמן קבוע בממוצע.
עבור פעם אחת על המערך עם קבוצה ריקה. עבור כל ערך, החזר
trueאם הוא כבר נמצא בקבוצה; אחרת, הוסף אותו. אם הלולאה מסתיימת, כל הערכים היו שונים.
פתרון
כפילות היא ערך שכבר נתקלת בו, והעבודה היא לענות במהירות על השאלה "האם כבר נתקלתי בזה?". השוואה של כל זוג עונה על השאלה, אבל עבור n = 10^4 מדובר ב-n(n-1)/2, כלומר בערך 5 × 10^7 השוואות. מיון מציב ערכים שווים זה לצד זה, וקבוצת גיבוב עונה על השאלה ב-O(1) בממוצע, מה שמאפשר מעבר יחיד.
מיין, ואז השווה בין שכנים
האינטואיציה
במערך ממוין, ערכים שווים נמצאים זה לצד זה. [3, 1, 4, 1, 5] מתמיין ל־[1, 1, 3, 4, 5], ושני הערכים 1 נוגעים זה בזה כעת. לכן, אחרי המיון משווים כל ערך רק לערך שמיד לפניו: n-1 השוואות במקום n(n-1)/2 ההשוואות שנדרשות כדי לנסות כל זוג.
אם אין שני איברים סמוכים שווים, אין שני ערכים שווים בשום מקום: כל ערך שנמצא בין שני עותקים של x בסדר ממוין חייב להיות גם גדול מ־x או שווה לו וגם קטן מ־x או שווה לו, ולכן הוא חייב להיות x נוסף.
פעולת המיון היא שקובעת את סיבוכיות הזמן: O(n log n). מיון nums במקום אינו דורש מערך נוסף, אבל מסדר מחדש את הקלט של הקוד שקרא לפונקציה; אם אסור לעשות זאת, יש למיין עותק, בעלות של O(n) מקום.
אלגוריתם
- מיין את
numsבסדר עולה. - עבור בלולאה על
iמ־1 עד לאינדקס האחרון. - אם
nums[i]שווה ל־nums[i-1], החזרtrue. - אחרי הלולאה, החזר
false.
def containsDuplicate(nums):
nums.sort()
# After sorting, equal values sit next to each other.
for i in range(1, len(nums)):
if nums[i] == nums[i - 1]:
return True
return Falseמעבר אחד עם קבוצת גיבוב
האינטואיציה
עבור על המערך פעם אחת ושמור כל ערך שכבר עברת עליו בקבוצת גיבוב. לפני הוספת ערך, בדוק אם הוא כבר נמצא בקבוצה. עבור [3, 1, 4, 1, 5] הקבוצה גדלה עד שהיא מכילה את {3, 1, 4}, וכשמגיע ה-1 השני הקבוצה כבר מכילה אותו, ולכן מחזירים true בלי לקרוא את 5.
הקבוצה תמיד מכילה בדיוק את הערכים שלפני המיקום הנוכחי, ולכן מציאה פירושה שהערך הנוכחי הופיע קודם, והגעה לסוף בלי מציאה פירושה שכל הערכים שונים.
חיפוש והוספה לקבוצת גיבוב נמשכים O(1) זמן בממוצע, ולכן המעבר כולו הוא O(n). המחיר הוא זיכרון: אם אין חזרה, הקבוצה תכיל בסופו של דבר את כל n הערכים.
אלגוריתם
- צרו קבוצת גיבוב ריקה
seen. - עבור כל ערך ב-
nums, אם הוא נמצא ב-seen, החזירוtrue. - אחרת הוסיפו אותו ל-
seen. - לאחר הלולאה, החזירו
false.
def containsDuplicate(nums):
seen = set()
for num in nums:
if num in seen:
return True
seen.add(num)
return False
מלכודות ומקרי קצה
הלוגיקה קצרה, ולכן הבאגים נמצאים בגבולות של הלולאות ובמה שמשווים.
- השוואה בין כל זוג כשהלולאה הפנימית מתחילה ב-
j = i. כך כל ערך תואם לעצמו, והתשובה היא תמידtrue. - השוואת איברים סמוכים בלי למיין קודם. ב-
[9, 1, 2, 3, 9]שני ערכי ה-9אינם סמוכים זה לזה. - התחלת לולאת האיברים הסמוכים באינדקס 0 וקריאה של
nums[-1]. התחילו ב-1, ומערך עם ערך אחד יחזיר כראויfalse. - התייחסות לערכים בעלי אותו ערך מוחלט כשווים, למשל באמצעות גיבוב של
abs(x).-4ו-4הם מספרים שונים. - כתיבת משווה למיון ב-C שמחזיר
x - y. כאן ההפרש נשאר בטווח של±2 × 10^9, מתחת לגבול שלint, כלומר2^31-1 = 2147483647, ולכן במקרה הזה הוא נכנס לטווח; עם ערכים שקרובים לגבולות שלint, מתרחשת גלישה והמיון יוצא שגוי. החזירו במקום זאת(x > y) - (x < y).
שאלות נפוצות3
מהי סיבוכיות הזמן של Contains Duplicate?
פתרון בעזרת קבוצת גיבוב פועל בזמן O(n) בממוצע ומשתמש במקום נוסף של O(n). מיון תחילה אורך זמן O(n log n) ואינו דורש מערך נוסף אם מותר לך לשנות את סדר הקלט. השוואה של כל זוג אורכת זמן O(n²).
האם תוכלו לפתור את Contains Duplicate בלי להשתמש במקום נוסף?
כן, אם מותר לך לשנות את סדר המערך: מיין אותו במקום והשווה כל ערך לשכן שלו. כך מחליפים את קבוצת O(n) בזמן של O(n log n). בלי לשנות את הסדר ובלי זיכרון נוסף, האפשרות היחידה שנותרה היא בדיקת זוגות ב-O(n²).
למה קבוצת גיבוב הופכת את הבדיקה למהירה?
קבוצת גיבוב מאחסנת ערכים לפי ערך הגיבוב שלהם, ולכן בדיקה אם היא מכילה ערך אורכת זמן קבוע בממוצע, במקום לסרוק אותה. כל איבר דורש חיפוש אחד והוספה אחת, ולכן המעבר כולו ליניארי.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def containsDuplicate(nums):
# כתבו כאן את הקודבדיקה #1
בדיקה #2
בדיקה #3
ארגומנט
nums = [3, 1, 4, 1, 5]
הפלט הצפוי
true