First Missing Positive

+10

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

פונקציה

firstMissingPositive(nums: integer-array) → integer

numsinteger-array: המספרים השלמים הלא ממוינים, שעשויים לחזור על עצמם ולהיות שליליים, אפס או גדולים מאוד
מחזירהinteger: המספר השלם החיובי הקטן ביותר שחסר ב-nums

אילוצים

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
הערכים אינם מופיעים בסדר מסוים וייתכן שיחזרו על עצמם.

דוגמאות

קלט: nums = [5, -2, 1, 3, 2, 9]
פלט: 4
הסבר: 1, 2 ו-3 נמצאים כולם במערך ו-4 לא, לכן התשובה היא 4. ל-5 ול-9 אין חשיבות ברגע שחסר ערך קטן יותר.

שאלת המשך

האם תוכל למצוא את התשובה בזמן O(n) תוך שימוש בזיכרון נוסף של O(1) בלבד?

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

נסה כל מועמד באמצעות סריקה מלאה

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

האינטואיציה

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

כאשר המערך מכיל את הערכים 1 עד n, כל מועמד נמצא בממוצע באמצע הסריקה, ולכן עבור n = 10^4 העלות היא בערך n²/2 = 5 × 10^7 השוואות.

אלגוריתם

הגדר את candidate ל־1.
סרוק את nums כדי למצוא איבר השווה ל־candidate, ועצור באיבר הראשון כזה.
אם אף איבר לא תואם, החזר את candidate.
אחרת, הוסף 1 ל־candidate וסרוק שוב. לעולם לא תחרוג מ־n+1.

def firstMissingPositive(nums):
    n = len(nums)
    # n values cannot cover all of 1..n+1, so one of these candidates is missing
    for candidate in range(1, n + 2):
        found = False
        for num in nums:
            if num == candidate:
                found = True
                break
        if not found:
            return candidate

סמן את הערכים מ־1 עד n במערך דגלים

האינטואיציה

מכיוון שהתשובה היא לכל היותר n+1, מדלגים על כל ערך שקטן מ-1 או גדול מ-n. מערך בוליאני present באורך n+1 מתעד את שאר הערכים, כך שערך כמו 10^9 לעולם לא נשמר. מחזירים את v הראשון מ-1 עד n שהדגל שלו הוא false, או n+1 אם כל הדגלים מסומנים.

בדוגמה הראשונה n = 6: הדגלים של 1, 2, 3 ו-5 מסומנים, על -2 ו-9 מדלגים, והדגל הראשון שאינו מסומן הוא 4. שתי סריקות ליניאריות נותנות זמן O(n), והדגלים צורכים זיכרון O(n).

אלגוריתם

צרו את present, מערך של n+1 דגלים שמוגדרים כ-false.
עבור כל ערך v ב-nums שעבורו 1 ≤ v ≤ n, הגדירו את present[v] כ-true.
החזירו את ערך v הראשון מ-1 עד n שהדגל שלו הוא false.
אם אין כזה, החזירו n+1.

def firstMissingPositive(nums):
    n = len(nums)
    # present[v] says whether v is in nums; only 1..n can matter
    present = [False] * (n + 1)
    for num in nums:
        if 1 <= num <= n:
            present[num] = True
    for v in range(1, n + 1):
        if not present[v]:
            return v
    return n + 1

הצב כל ערך במשבצת משלו

האינטואיציה

הערך v שייך לאינדקס v-1. כשכל הערכים מ-1 עד n נמצאים במקומם, האינדקס הראשון i שאינו מכיל את i+1 מצביע על התשובה.

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

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

כל החלפה מציבה ערך אחד במקומו לצמיתות, ולכן הלולאות הפנימיות מבצעות לכל היותר n החלפות בסך הכול: זמן O(n), וזיכרון O(1), למעט ב-R, שמעתיקה את הווקטור שהיא משנה.

אלגוריתם

עבור כל אינדקס i מ-0 עד n-1:
כל עוד 1 ≤ nums[i] ≤ n וגם nums[nums[i]-1] ≠ nums[i], החלף את nums[i] עם nums[nums[i]-1].
לאחר שלב ההצבה, מצא את האינדקס הראשון i שבו nums[i] ≠ i+1 והחזר את i+1.
אם כל תא מכיל את הערך שלו, החזר n+1.

def firstMissingPositive(nums):
    n = len(nums)
    for i in range(n):
        # Keep swapping until slot i holds a value that has no slot or is already home
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            home = nums[i] - 1
            nums[i], nums[home] = nums[home], nums[i]
    # The first slot that does not hold its own value names the answer
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

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

עצירת ההחלפות כאשר nums[i] == i+1 במקום כאשר הערך כבר נמצא במקומו. עם [1, 1], שני הערכים 1 יוחלפו זה בזה לנצח.
ביצוע החלפה באמצעות if במקום while. בדוגמה הראשונה, הערך 2 שחוזר מאינדקס 4 לעולם לא מגיע לאינדקס 1, ואתם מחזירים 2 במקום 4.
כתיבת nums[i] = nums[nums[i]-1] ואז גישה לאינדקס שוב באמצעות nums[i], שקוראת את אינדקס היעד לאחר שהוא השתנה. שמרו קודם את אינדקס היעד.
דילוג על בדיקת הטווח, ששולחת את 0, ‏-2 או 10^9 לאינדקס מחוץ למערך.
החזרת n כאשר כל המקומות נכונים. עבור [4, 2, 1, 3] התשובה היא 5.

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

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

פתרון המיקום פועל בזמן O(n) ובתוספת זיכרון של O(1). לולאת ה-while נמצאת בתוך לולאת for, אבל כל החלפה מציבה ערך באינדקס הסופי שלו, כך שבכל הריצה מתבצעות לכל היותר n החלפות. גרסת מערך הדגלים היא בזמן O(n) ובזיכרון של O(n), וסריקה עבור כל מועמד היא בסיבוכיות O(n²).

מדוע התשובה לעולם אינה גדולה מ־n+1?

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

האם הפתרון במקום משנה את מערך הקלט?

כן, היא מסדרת מחדש את הערכים. אם הקוד הקורא זקוק לסדר המקורי, צריך להעתיק תחילה את המערך, מה שמחזיר את צריכת הזיכרון הנוספת ל־O(n). שיטה נוספת שפועלת במקום מחליפה כל ערך שמחוץ לטווח 1 עד n ב־n+1, ואז מסמנת ש־v קיים על ידי הפיכת nums[v-1] לשלילי; גם היא משנה את המערך.

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

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנט

nums = [5, -2, 1, 3, 2, 9]

הפלט הצפוי

First Missing Positive

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

נסה כל מועמד באמצעות סריקה מלאה

סמן את הערכים מ־1 עד n במערך דגלים

הצב כל ערך במשבצת משלו

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

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

בעיות דומות