מציאת המספר החיובי הקטן ביותר החסר

נתון מערך חד-ממדי arr לא ממוין מלא במספרים שלמים. יש להחזיר את המספר החיובי הקטן ביותר שלא נמצא במערך (0 אינו מספר חיובי).

לדוגמה, עבור המערך הבא:

012345
1-362015

המספר החיובי הקטן ביותר שלא נמצא במערך הוא 3 (1 ו-2 נמצאים במערך, אבל 3 לא).

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

אילוצים:
  • מותר לשנות את המערך במהלך השיטה, ואין צורך להחזיר אותו למצבו המקורי בסיומה.
דוגמה 1:
קלט: 
arr = [1, -3, 6, 2, 0, 15]
פלט: 
3

הסבר: המספרים החיוביים 1 ו-2 נמצאים במערך, אבל 3 הוא המספר החיובי הקטן ביותר שחסר

דוגמה 2:
קלט: 
arr = [1, 1, 1, 1]
פלט: 
2

הסבר: המספר 1 מופיע במערך מספר פעמים, והמספר החיובי הקטן ביותר שחסר הוא 2

דוגמה 3:
קלט: 
arr = [1, 2, 3, 4]
פלט: 
5

הסבר: המערך מכיל את כל המספרים החיוביים מ-1 עד 4, ולכן 5 הוא המספר החיובי הקטן ביותר שחסר

דוגמה 4:
קלט: 
arr = [5, -1, 3, 1, 0, -2, 2]
פלט: 
4

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

דוגמה 5:
קלט: 
arr = [7, 8, 9, 11, 12, 14]
פלט: 
1

הסבר: כל המספרים במערך גדולים מ-1, ולכן 1 הוא המספר החיובי הקטן ביותר שחסר

דוגמה 6:
קלט: 
arr = [-5, -4, -3, -2, -1]
פלט: 
1

הסבר: כל המספרים במערך שליליים, ולכן 1 הוא המספר החיובי הקטן ביותר שחסר

דוגמה 7:
קלט: 
arr = [2, 3, 4, 5, 6]
פלט: 
1

הסבר: המערך מתחיל מ-2, ולכן 1 הוא המספר החיובי הקטן ביותר שחסר

דוגמה 8:
קלט: 
arr = [1, 1000000]
פלט: 
2

הסבר: למרות שיש מספר גדול מאוד במערך, 2 הוא המספר החיובי הקטן ביותר שחסר

Loading...
נשמרLn 1, Col 1

קלט:

arr = [1, -3, 6, 2, 0, 15]

הפלט המבוקש:

3