Single Number
ניתנת לך רשימה nums שבה כל ערך מופיע בדיוק פעמיים, למעט ערך אחד שמופיע פעם אחת בלבד. החזר את הערך שמופיע פעם אחת.
פונקציה
- numsinteger-array
- רשימה שבה כל ערך מופיע פעמיים, פרט לאחד
- מחזירהinteger
- הערך שמופיע פעם אחת בלבד
אילוצים
1 ≤ nums.length < 104-104 ≤ nums[i] ≤ 104- כל ערך מופיע בדיוק פעמיים, למעט ערך אחד שמופיע בדיוק פעם אחת.
דוגמאות
- קלט
- nums = [8, 3, 8]
- פלט
- 3
- הסבר
- 8 מופיע פעמיים ו־3 מופיע פעם אחת, לכן התשובה היא 3.
- קלט
- nums = [5, -2, 7, 5, 7]
- פלט
- -2
- הסבר
- 5 ו-7 מופיעים פעמיים כל אחד, ו--2 הוא הערך היחיד שמופיע פעם אחת. תשובה שלילית מוצאים באותה הדרך כמו תשובה חיובית.
- קלט
- nums = [42]
- פלט
- 42
- הסבר
- לרשימה עם ערך אחד אין זוגות כלל, ולכן הערך הזה הוא התשובה.
+13 בדיקות נסתרות בשליחה
שאלת המשך
מה אם כל ערך הופיע שלוש פעמים, מלבד אחד? XOR לבדו כבר לא מבטל את השלשות. האם עדיין אפשר למצוא את הערך היחיד בזמן O(n) ובזיכרון נוסף של O(1)?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
אם אפשר היה לגרום לכל זוג של ערכים שווים להיעלם, רק התשובה הייתה נשארת. האם יש פעולה שהופכת שני מספרים שווים לכלום?
XOR עושה:
x ^ xהוא0ו-x ^ 0הואx. הוא גם אינו תלוי בסדר, כך ששני העותקים של ערך לא צריכים להיות זה לצד זה כדי להתבטל.השאר משתנה אחד שמתחיל ב־
0. בצע XOR על כל ערך ב־numsוהכנס אותו אליו, ואז החזר אותו. אין צורך במפה או במיון.
פתרון
מציאת הערך היחיד שאין לו בן זוג היא בעיית ספירה, ומפת גיבוב סופרת כל ערך במעבר אחד. החיסרון הוא הזיכרון: המפה גדלה יחד עם הרשימה. XOR מבטל את הצורך לספור בכלל, כי XOR של ערך עם עצמו נותן 0. בצעו XOR על כל הרשימה, וכל זוג יבטל את עצמו, וישאיר את הערך היחיד במעבר אחד עם משתנה אחד.
ספרו כל ערך באמצעות סריקה
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
עבור על כל ערך בתורו וסרוק את הרשימה כולה כדי לספור כמה פעמים הוא מופיע. ערך מתוך זוג נספר 2 פעמים. הערך היחיד נספר פעם אחת, לכן החזר את הערך הראשון שמספר הפעמים שהוא מופיע הוא 1.
זה נכון כי הספירות נובעות ישירות מההגדרה של התשובה, ולא נדרש זיכרון נוסף מעבר למונה.
זה איטי כי כל אחד מ־n הערכים גורם לסריקה מלאה של n ערכים. כאשר הערך היחיד נמצא בסוף רשימה של 9,999 איברים, מדובר בכמעט 10^8 השוואות.
אלגוריתם
- עברי בלולאה על כל ערך ב־
nums. - סרוק את הרשימה כולה וספור את הערכים ששווים לו.
- אם הספירה היא 1, החזר את הערך הזה.
def singleNumber(nums):
for value in nums:
# count() scans the whole list: O(n) per value.
if nums.count(value) == 1:
return value
return 0ספירה באמצעות מפת גיבוב
האינטואיציה
סריקה מחדש של הרשימה עבור כל ערך גורמת לחזרה על העבודה. במקום זאת, ספרו את כל הערכים במעבר אחד: מפת גיבוב מערך למספר הפעמים שהוא מופיע, כאשר בכל שלב מוסיפים 1 למספר הפעמים של הערך הנוכחי.
עבור [5, -2, 7, 5, 7] המפה מסתיימת כך: 5 → 2, -2 → 1, 7 → 2. מעבר שני על המפה מוצא את הרשומה שמספר הפעמים שלה הוא 1, והיא -2.
כל ערך דורש עדכון אחד במפה, ולכן זמן הריצה הוא O(n). המפה מכילה בערך n/2 רשומות, כלומר נדרשת זיכרון נוסף בהיקף של O(n). ב-C, שאין בה מפה מובנית, מערך של מונים שהאינדקס שלו הוא value + 10^4 ממלא את אותו התפקיד, כי הערכים קטנים.
אלגוריתם
- צרו מפה ריקה מערכים לספירות.
- עבור כל ערך ב־
nums, הוסיפו 1 לספירה שלו. - עברו על המפה והחזירו את הערך שהספירה שלו היא 1.
def singleNumber(nums):
counts = {}
for value in nums:
counts[value] = counts.get(value, 0) + 1
for value, count in counts.items():
if count == 1:
return value
return 0בצע XOR על כל הערכים
האינטואיציה
XOR משווה בין שני מספרים ביט אחר ביט ומגדיר ביט במקומות שבהם הם שונים. מכאן נובעות שלוש עובדות: x ^ x = 0, x ^ 0 = x, וסדר הפעולות אינו משנה.
לכן בצע XOR על כל הרשימה לתוך משתנה אחד שמתחיל ב־0. אפשר לקבץ מחדש את הפעולות כך שכל זוג יפגוש את התאום שלו, וכל זוג יהפוך ל־0. מה שנותר הוא 0 ^ single, שהוא הערך היחיד. עבור [8, 3, 8]: 0 ^ 8 = 8, אחר כך 8 ^ 3 = 11, ואז 11 ^ 8 = 3.
גם מספרים שליליים עובדים. XOR פועל על הביטים של ייצוג משלים ל־2, ולשני מספרים שליליים שווים יש ביטים זהים, ולכן הם מבטלים זה את זה כמו כל זוג אחר. הלולאה קוראת כל ערך פעם אחת ושומרת משתנה אחד: זמן O(n) וזיכרון נוסף O(1).
אלגוריתם
- הגדר את
resultל־0. - עבור כל ערך ב־
nums, הגדר אתresultל־result ^ value. - החזר את
result.
def singleNumber(nums):
result = 0
for value in nums:
result ^= value
return result
מלכודות ומקרי קצה
לולאת XOR קצרה, לכן הטעויות מסתתרות בנקודת ההתחלה שלה ובחלופות שאנשים פונים אליהן.
- מתחילים את
resultב-nums[0]ואז עוברים בלולאה על כל הערכים, כולל אינדקס 0. הערך הראשון עובר פעולת XOR פעמיים ומבטל את עצמו. מתחילים ב-0, או מדלגים על אינדקס 0. - ממיינים ומשווים בין איברים שכנים בקפיצות של שניים, ואז שוכחים שהערך היחיד יכול להיות האיבר האחרון. ב-
[1, 1, 2]אין זוג לא תואם, והתשובה היא 2 שנשאר. - משתמשים ב-
2 × sum(distinct values) - sum(nums). התוצאה נכונה, אבל קבוצת הערכים הייחודיים צורכתO(n)זיכרון, בניגוד לפתרון XOR שנמנע מכך. - מצפים ש-XOR יעבוד גם עבור מספר מופעים אחר. הוא מבטל ערכים שמופיעים מספר זוגי של פעמים. אם ערך הופיע שלוש פעמים, עותק אחד יישאר ויקלקל את התשובה.
שאלות נפוצות4
מהי סיבוכיות הזמן של Single Number?
פתרון XOR פועל בזמן O(n) ומשתמש ב־O(1) מקום נוסף, מכיוון שהוא קורא כל ערך פעם אחת ושומר משתנה אחד. גם מפת גיבוב פועלת בזמן O(n), אך דורשת זיכרון בגודל O(n). ספירת כל ערך באמצעות סריקה חדשה דורשת זמן O(n²).
למה XOR פותר את בעיית המספר היחיד?
ביצוע XOR למספר עם עצמו נותן 0, ביצוע XOR עם 0 לא משנה דבר, וסדר הפעולות אינו משנה. לכן, כשמבצעים XOR על הרשימה כולה, אפשר לקבץ כל זוג יחד והוא מתבטל ל־0. נשאר רק הערך שאין לו בן זוג.
האם טריק ה-XOR עובד עם מספרים שליליים?
כן. XOR פועל על הביטים שבהם המספר מאוחסן, ומספרים שליליים מאוחסנים במשלים ל-2. לשני מספרים שליליים שווים יש ביטים זהים, ולכן הם מבטלים זה את זה בדיוק כמו מספרים חיוביים. ב-[5, -2, 7, 5, 7] התוצאה היא -2.
איך פותרים את זה כששאר הערכים מופיעים שלוש פעמים?
XOR מבצע ביטול של זוגות, לא של שלשות, ולכן הוא נכשל במקרה הזה. במקום זאת, ספור כמה ערכים כוללים כל אחד מ־32 הביטים. עבור כל ביט, השארית של הספירה בחלוקה ל־3 היא הביט של הערך היחיד, כי השלשות מוסיפות כפולות של 3. גם כך זמן הריצה הוא O(n) ונעשה שימוש בזיכרון נוסף של O(1).
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def singleNumber(nums):
# כתבו כאן קודמקרה 1
מקרה 2
מקרה 3
קלט
nums = [8, 3, 8]
צפוי
3