Missing Number

Q: מהי סיבוכיות הזמן של Missing Number?

פתרונות הסכום וה-XOR פועלים שניהם בזמן O(n) ובשטח נוסף של O(1) , מכיוון שהם קוראים כל ערך פעם אחת ושומרים מספר אחד. חיפוש ברשימה עבור כל מועמד דורש O(n²) . מיון תחילה וחיפוש הפער דורשים O(n log n) .

קלמניפולציית ביטים מתמטיקה וסימולציה

+10

ניתנת לך רשימה nums של n מספרים שלמים שונים, שכל אחד מהם נמצא בין 0 ל־n. הטווח מ־0 עד n כולל n+1 מספרים, ולכן בדיוק אחד מהם אינו מופיע ברשימה. החזר את המספר החסר.

פונקציה

missingNumber(nums: integer-array) → integer

numsinteger-array: n מספרים שלמים שונים מהטווח 0 עד n, בכל סדר
מחזירהinteger: המספר היחיד מ־0 עד n שאינו נמצא ב־nums

אילוצים

n == nums.length
1 ≤ n ≤ 10⁴
0 ≤ nums[i] ≤ n
כל הערכים ב־nums שונים זה מזה.

דוגמאות

קלט: nums = [4, 2, 0, 1]
פלט: 3
הסבר: ברשימה יש 4 ערכים, לכן הטווח הוא מ־0 עד 4. היא מכילה את 0, 1, 2 ו־4, ו־3 הוא המספר היחיד שאין לו התאמה.

שאלת המשך

אם הרשימה הייתה ממוינת, האם היית יכול למצוא את המספר החסר בזמן O(log n) באמצעות חיפוש בינארי?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

אתה יודע בדיוק מה הרשימה צריכה להכיל: כל מספר שלם מ־0 עד n. חיפוש של כל אחד מהמספרים האלה בזה אחר זה עובד, אבל חוזר על סריקה מלאה עבור כל מספר. במקום זאת, דחוס את כל הטווח ואת הרשימה לערך סיכום אחד לכל אחד, הסכום או פעולת XOR, וההפרש בין השניים הוא המספר החסר. כך נדרשת מעבר אחד וללא זיכרון נוסף.

בדוק כל מועמד

נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר

האינטואיציה

התשובה היא אחד מ־n+1 המספרים שבין 0 ל־n. עוברים עליהם לפי הסדר וסורקים את הרשימה כדי לחפש כל אחד מהם. המועמד הראשון שאף ערך אינו תואם לו הוא המספר החסר.

זה נכון כי כל מספר בטווח נמצא ברשימה או שהוא התשובה, וברשימה אין כפילויות, ולכן בדיוק מועמד אחד נכשל בחיפוש.

השיטה איטית כי בדיקת כל מועמד דורשת סריקה של עד n ערכים. כשהפער נמצא סמוך לקצה העליון, מחפשים כמעט כל מועמד: עבור n = 10^4 וכשהפער סמוך לסוף, מדובר בכ־5 × 10^7 השוואות. הכפלת אורך הרשימה מגדילה את העבודה פי ארבעה.

אלגוריתם

הרץ בלולאה את candidate מ־0 ועד n, כולל.
סרוק את nums כדי למצוא ערך השווה ל־candidate.
אם הסריקה מוצאת אותו, המשך למועמד הבא.
אם הסריקה מסתיימת ללא התאמה, החזר את candidate.

def missingNumber(nums):
    n = len(nums)
    for candidate in range(n + 1):
        # "in" on a list scans it from the start: O(n) per candidate.
        if candidate not in nums:
            return candidate
    return -1

חסר את הסכום מהסכום הצפוי

האינטואיציה

אם שום דבר לא היה חסר, הרשימה הייתה מכילה כל מספר מ־0 עד n, והסכום שלהם הוא n(n+1)/2. הרשימה בפועל היא הקבוצה המלאה הזו לאחר שהוצא ממנה מספר אחד, ולכן הסכום שלה קטן בדיוק באותו מספר.

עבור [4, 2, 0, 1], הערך של n הוא 4, וסכום הטווח המלא הוא 4 × 5 / 2 = 10. סכום הרשימה הוא 7, ו־10 פחות 7 שווה 3.

מעבר אחד מסכם את איברי הרשימה, ולכן זמן הריצה הוא O(n), וצריך לשמור רק סכום מצטבר אחד. כאן הסכום המלא הוא לכל היותר בערך 5 × 10^7, וזה נכנס למספר שלם בן 32 סיביות. עבור ערכים גדולים בהרבה של n, הנוסחה חורגת מטווח הייצוג של מספר שלם בן 32 סיביות, ולכן הגרסאות ב־Java, C, C++, C# ו־Rust מבצעות את החישוב ב־64 סיביות.

אלגוריתם

נסמן את אורך nums ב־n.
חשב את הסכום המלא n(n+1)/2.
חבר את כל הערכים ב־nums.
החזר את הסכום המלא פחות סכום הרשימה.

def missingNumber(nums):
    n = len(nums)
    expected = n * (n + 1) // 2
    return expected - sum(nums)

XOR את האינדקסים עם הערכים

האינטואיציה

XOR מבטל זוגות. a ^ a הוא 0, a ^ 0 הוא a, וסדר הפעולות לא משנה. לכן, אם מבצעים XOR על אוסף מספרים שבו כל מספר מופיע פעמיים, מלבד ערך אחד, הזוגות מתבטלים והערך הזה נשאר.

בנה אוסף כזה מתוך הבעיה: האינדקסים 0 עד n יחד עם הערכים ב-nums. מספר שנמצא ברשימה מופיע פעם אחת כאינדקס ופעם אחת כערך, ולכן הוא מתבטל. המספר החסר מופיע רק כאינדקס, ולכן הוא נשאר. הלולאה עוברת על האינדקסים 0 עד n-1, לכן התחל את התוצאה ב-n כדי לכלול את האחרון.

עבור [4, 2, 0, 1]: התחל ב-4, ואז בצע XOR עם 0 ו-4, עם 1 ו-2, עם 2 ו-0, ועם 3 ו-1. ה-4, ה-2, ה-1 וה-0 מתבטלים כולם, ו-3 נשאר. זהו מעבר אחד עם ערך מצטבר אחד, ובניגוד לסכום, הוא לעולם לא גדל מעבר לביטים שבהם n כבר משתמש, ולכן הוא לא יכול לגלוש.

אלגוריתם

הגדר את result ל־n, האורך של nums.
עבור כל אינדקס i, בצע XOR בין result לבין i ובין result לבין nums[i].
החזר את result.

def missingNumber(nums):
    # Start with n, the one index the loop below never reaches.
    result = len(nums)
    for i, value in enumerate(nums):
        result ^= i ^ value
    return result

מלכודות ומקרי קצה

רוב התשובות השגויות נובעות משני הקצוות של הטווח.

שוכחים שגם n עצמו עשוי להיות חסר. ב־[0, 1, 2] התשובה היא 3, שאינו אינדקס ברשימה. גרסת ה־XOR חייבת להתחיל ב־n, וסריקה ממוינת שמחפשת את nums[i] != i הראשון חייבת להחזיר את n כאשר כל המיקומים תואמים.
משתמשים בגודל טווח שגוי. המספרים נעים מ־0 עד n, כלומר יש n+1 מספרים, ולכן הסכום המלא הוא n(n+1)/2, ולא (n-1)n/2.
מניחים ש־0 תמיד נמצא. ב־[1] התשובה היא 0, וקוד שמתחיל את החיפוש ב־1 מפספס אותו.
גלישה בחישוב הסכום. בחשבון של 32 סיביות, המכפלה n(n+1) גולשת כאשר n עובר בערך את 46,000, לפני שהחלוקה ב־2 יכולה לעזור, והערך n(n+1)/2 עצמו מפסיק להתאים בסביבות 65,000. השתמשו בחשבון של 64 סיביות או ב־XOR.

שאלות נפוצות3

מהי סיבוכיות הזמן של Missing Number?

פתרונות הסכום וה-XOR פועלים שניהם בזמן O(n) ובשטח נוסף של O(1), מכיוון שהם קוראים כל ערך פעם אחת ושומרים מספר אחד. חיפוש ברשימה עבור כל מועמד דורש O(n²). מיון תחילה וחיפוש הפער דורשים O(n log n).

למה XOR מוצא את המספר החסר?

ביצוע XOR למספר עם עצמו נותן 0, ביצוע XOR עם 0 לא משנה דבר, ולסדר אין חשיבות. כשמבצעים XOR לכל האינדקסים מ־0 עד n יחד עם כל הערכים, כל מספר שנמצא ברשימה מופיע פעמיים ומבטל את עצמו. המספר החסר מופיע רק פעם אחת, כאינדקס, ולכן הוא התוצאה.

האם כדאי להשתמש בנוסחת הסכום או ב-XOR?

שתיהן מבצעות מעבר אחד ודורשות זיכרון קבוע. קל יותר להסביר את הסכום, אבל בחשבון 32-ביט המכפלה n(n+1) גורמת לגלישה ברגע ש-n עולה על כ-46,000, ולכן צריך להשתמש בחשבון 64-ביט. XOR לעולם לא גורם לגלישה. ב-Python, ב-Ruby ובשפות אחרות עם מספרים שלמים בלתי מוגבלים, ההבדל נעלם.

def missingNumber(nums):
    # כתבו כאן את הקוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנט

nums = [4, 2, 0, 1]

הפלט הצפוי

Missing Number

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

בדוק כל מועמד

חסר את הסכום מהסכום הצפוי

XOR את האינדקסים עם הערכים

מלכודות ומקרי קצה

שאלות נפוצות3

בעיות דומות