Remove Duplicates from Sorted Array
ניתן לך מערך של מספרים שלמים nums שממוינים בסדר לא יורד, כך שערכים שווים נמצאים זה לצד זה. החזר את הערכים הייחודיים של nums, כל אחד פעם אחת, לפי סדר הופעתם. לדוגמה, [2, 2, 5] נותן [2, 5].
פונקציה
- numsinteger-array
- המספרים השלמים, ממוינים בסדר לא יורד
- מחזירהinteger-array
- הערכים השונים של nums, בסדר עולה
אילוצים
1 ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 104numsמסודר בסדר לא יורד.
דוגמאות
- קלט
- nums = [1, 1, 2, 3, 3, 3]
- פלט
- [1, 2, 3]
- הסבר
1מופיע פעמיים ו־3מופיע שלוש פעמים. אם משאירים אחד מכל אחד, מתקבל[1, 2, 3].
- קלט
- nums = [-2, 0, 0, 5]
- פלט
- [-2, 0, 5]
- הסבר
- רק
0חוזר על עצמו. ערכים שליליים פועלים באותו אופן, לכן התשובה היא[-2, 0, 5].
- קלט
- nums = [7, 7, 7]
- פלט
- [7]
- הסבר
- כל הערכים הם
7, ולכן נשאר רק7אחד.
+15 בדיקות נסתרות בשליחה
שאלת המשך
האם תוכל לעשות זאת עם זיכרון נוסף של O(1), על ידי כתיבה מחדש של nums במקום כדי לא לבנות מערך נוסף?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
מכיוון ש-
numsממוינת, כל העותקים של ערך יוצרים רצף אחד. איך אפשר לדעת שערך הוא הראשון ברצף שלו בלי לזכור כל ערך שראית?ערך מתחיל רצף חדש בדיוק כאשר הוא שונה מהערך האחרון ששמרת. לכן תמיד משווים רק לערך אחד, ואפשר לדרוס את המערך מההתחלה תוך כדי התקדמות.
יש לשמור אינדקס כתיבה
k, שמתחיל ב־1 כיnums[0]נשמר תמיד. יש לקרוא כל ערך מאוחר יותר; כאשר הוא שונה מ־nums[k-1], יש להעתיק אותו אלnums[k]ולהוסיף 1 ל־k. יש להחזיר אתkהערכים הראשונים.
פתרון
הסרת כפילויות ממערך שרירותי פירושה לזכור כל ערך שראית. קלט ממוין מייתר את הצורך הזה: עותקים של ערך נמצאים זה לצד זה, ולכן ערך חדש בדיוק כשהוא שונה מהערך האחרון ששמרת. כך המשימה הופכת למעבר יחיד עם שני אינדקסים וללא זיכרון נוסף.
זכרו ערכים שנצפו בקבוצת גיבוב
האינטואיציה
עבור על nums ושמור קבוצה של הערכים שכבר הוספת לתשובה. כשערך לא נמצא בקבוצה, הוסף אותו לסוף התשובה והוסף אותו לקבוצה; כשהוא נמצא בה, דלג עליו. עבור [1, 1, 2, 3, 3, 3] התשובה גדלה ל־[1], אחר כך ל־[1, 2], ואז ל־[1, 2, 3], וכל עותק נוסף מדולג.
כל ערך מתווסף בפעם הראשונה שהוא מופיע, ולעולם לא שוב, בסדר שבו פוגשים אותו, ולכן התשובה נכונה. הגישה הזאת אינה משתמשת כלל בעובדה ש־nums ממוין; היא הייתה עובדת על כל מערך.
חיפושים בקבוצה אורכים O(1) בממוצע, ולכן המעבר אורך O(n) זמן, אבל גם הקבוצה וגם התשובה יכולות להכיל כל אחת n ערכים: נדרש מרחב נוסף של O(n). ב־C, שבה אין קבוצה מובנית, מערך של דגלים עבור 2 × 10^4 + 1 הערכים האפשריים עושה את אותה העבודה.
אלגוריתם
- צרו קבוצה ריקה
seenורשימה ריקהresult. - עבור כל ערך ב-
nums, בדקו אם הוא נמצא ב-seen. - אם לא, הוסיפו אותו ל-
seenוצרפו אותו לסוףresult. - החזירו את
result.
def removeDuplicates(nums):
seen = set()
result = []
for num in nums:
if num not in seen:
seen.add(num)
result.append(num)
return resultצמצום במקום באמצעות מצביע כתיבה
האינטואיציה
בקלט ממוין, כל העותקים של ערך מופיעים ברצף אחד, ולכן ערך חדש בדיוק כשהוא שונה מהערך האחרון ששמרת. לשם כך נדרשת השוואה אחת, ולא קבוצה.
השתמש בשני אינדקסים. אינדקס הקריאה i עובר על כל הערכים. אינדקס הכתיבה k מסמן את סוף החלק שנשמר: nums[0] עד nums[k-1] מכילים תמיד את הערכים הייחודיים שנמצאו עד כה. התחל עם k = 1, מכיוון שהערך הראשון נשמר תמיד. כאשר nums[i] שונה מ־nums[k-1], העתק אותו אל nums[k] והקדם את k.
עבור [1, 1, 2, 3, 3, 3]: i = 1 קורא את ה־1 השני, ולא קורה דבר. i = 2 קורא את 2, ששונה מ־nums[0] = 1, ולכן הוא נכתב באינדקס 1 ו־k הופך ל־2. i = 3 כותב את 3 באינדקס 2 ו־k הופך ל־3. שני ערכי ה־3 האחרונים תואמים ל־nums[2] ונפסחים. כעת שלושת המקומות הראשונים מכילים את [1, 2, 3].
הכתיבה לעולם אינה עוקפת את הקריאה, כי k תמיד קטן מ־i או שווה לו, ולכן לעולם אינך דורס ערך לפני שקראת אותו. מעבר יחיד דורש זמן O(n), ומלבד הערכים המוחזרים משתמשים בשני מספרים שלמים: מקום נוסף O(1).
אלגוריתם
- הגדר
k = 1: תמיד שומרים אתnums[0]. - עבור בלולאה על
iמ־1 ועד לאינדקס האחרון. - אם
nums[i]שונה מ־nums[k-1], הגדרnums[k] = nums[i]והוסף 1 ל־k. - החזר את
kהערכים הראשונים שלnums.
def removeDuplicates(nums):
# nums[0:k] holds the distinct values found so far, in order.
k = 1
for i in range(1, len(nums)):
if nums[i] != nums[k - 1]:
nums[k] = nums[i]
k += 1
return nums[:k]
מלכודות ומקרי קצה
מצביע הכתיבה קצר, והשגיאות בו קשורות לערך שצריך להשוות אליו.
- השוואה בין
nums[i]לביןnums[i+1]בזמן ש-iמתקדם עד לאינדקס האחרון. ההשוואה האחרונה קוראת מיקום אחד מעבר לסוף המערך. - התחלה של
kב-0. כך הערך הראשון מושווה ל-nums[-1], שנמצא מחוץ לטווח, או שב-Python הוא האיבר האחרון. - החזרת המערך כולו במקום רק
kהערכים הראשונים שלו. הזנב עדיין מכיל ערכים ישנים, ולכן[1, 1, 2]יוחזר בתור[1, 2, 2]. - בניית התשובה באמצעות מעבר על קבוצת גיבוב. ברוב השפות, קבוצת גיבוב אינה שומרת על סדר, ולכן הערכים עלולים להופיע בסדר מעורבב; במקום זאת, יש להוסיף כל ערך לרשימה כשנתקלים בו לראשונה.
- ב-Lua וב-R, המערכים מתחילים ב-1. החלק שנשמר הוא
nums[1]עדnums[k], וההשוואה היא ל-nums[k], ולא ל-nums[k-1].
שאלות נפוצות4
מהי סיבוכיות הזמן של הסרת כפילויות ממערך ממוין?
פתרון מצביע הכתיבה קורא כל ערך פעם אחת, ולכן זמן הריצה שלו הוא O(n). מלבד הערכים שהוא מחזיר, הוא משתמש ב־O(1) מקום נוסף: שני אינדקסים.
למה צריך למיין את המערך?
מיון מציב את כל העותקים של ערך ברצף אחד, ולכן ערך הוא חדש בדיוק כשהוא שונה מהערך האחרון שנשמר. במערך לא ממוין עותק יכול להופיע הרחק מהעותק הראשון, וצריך מערך גיבוב כדי לזכור כל ערך שנראה, דבר שדורש O(n) מקום נוסף.
איך מסירים כפילויות במקום, בלי להשתמש בזיכרון נוסף?
החזק אינדקס כתיבה k לצד אינדקס הקריאה. המקומות הראשונים עד k מכילים את הערכים הייחודיים שנקראו עד כה. כאשר הערך שקראת שונה מ־nums[k-1], העתק אותו אל nums[k] וקדם את k. אינדקס הכתיבה לעולם אינו עובר את אינדקס הקריאה, כך ששום דבר לא נדרס לפני שקוראים אותו.
איך תאפשר לכל ערך להופיע לכל היותר פעמיים?
יש להשוות לערך שנמצא שני מקומות אחורה בחלק שנשמר במקום למקום אחד אחורה: יש להעתיק את nums[i] כאשר k < 2 או כאשר הוא שונה מ־nums[k-2]. אם הוא שווה ל־nums[k-2], החלק שנשמר כבר מסתיים בשני עותקים שלו. אותו רעיון מאפשר לשמור לכל היותר m עותקים באמצעות nums[k-m].
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def removeDuplicates(nums):
# כתבו כאן את הקודמקרה 1
מקרה 2
מקרה 3
קלט
nums = [1, 1, 2, 3, 3, 3]
צפוי
[1, 2, 3]