Intersection of Two Arrays
מקבלים שני מערכים של מספרים שלמים, nums1 ו־nums2. יש להחזיר את כל הערכים שמופיעים בשני המערכים, ממוינים בסדר עולה. כל ערך משותף מופיע בתשובה פעם אחת, בלי קשר למספר הפעמים שהוא חוזר בכל אחד מהמערכים.
פונקציה
- nums1integer-array
- הרשימה הראשונה של המספרים השלמים
- nums2integer-array
- רשימת המספרים השלמים השנייה
- מחזירהinteger-array
- הערכים שנמצאים בשתי הרשימות, כל אחד פעם אחת, בסדר עולה
אילוצים
1 ≤ nums1.length, nums2.length ≤ 5000-105 ≤ nums1[i], nums2[i] ≤ 105- לפחות ערך אחד מופיע בשני המערכים.
דוגמאות
- קלט
- nums1 = [6, 2, 9, 2, 4]nums2 = [4, 4, 1, 6]
- פלט
- [4, 6]
- הסבר
4ו-6נמצאים בשני המערכים.4מופיע פעמיים ב-nums2אבל מצוין פעם אחת, ו-2ו-9לעולם אינם מופיעים ב-nums2.
- קלט
- nums1 = [-3, 0, 7]nums2 = [7, -3, -3, 5]
- פלט
- [-3, 7]
- הסבר
-3ו-7נמצאים בשני המערכים. בסדר עולה,-3מופיע ראשון, אף על פי ש-7מופיע ראשון ב-nums2.
+16 בדיקות נסתרות בשליחה
שאלת המשך
מה אם nums1 מכיל 10 ערכים ו־nums2 מכיל מיליון ערכים, שכבר ממוינים? באיזו גישה היית בוחר, והאם חיפוש בינארי יכול להיות מהיר יותר מסריקה מלאה?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
עבור כל ערך של
nums1אפשר לסרוק את כל הערכים שלnums2. כשיש 5000 ערכים בכל מערך, מדובר בעד2.5 × 10^7השוואות. איזו שאלה את/ה שואל/ת שוב ושוב?השאלה החוזרת היא "האם הערך הזה נמצא במערך השני?". קבוצת גיבוב שנבנתה ממערך אחד עונה עליה בזמן קבוע בממוצע.
בנה קבוצה מתוך
nums1. עבור עלnums2; כשערך נמצא בקבוצה, הוסף אותו לתשובה והסר אותו מהקבוצה, כך שלא ניתן יהיה להוסיף עותק מאוחר יותר. מיין את התשובה לפני שתחזיר אותה.
פתרון
שני פרטים מכריעים בבעיה הזאת: ערך שמופיע בשני הצדדים עדיין נכנס לתשובה פעם אחת בלבד, והתשובה חייבת להיות ממוינת. השוואה של כל זוג עובדת, אבל דורשת n × m השוואות — 2.5 × 10^7 כשבשני המערכים יש 5000 ערכים. מיון שני המערכים מאפשר לשני מצביעים למצוא את הערכים המשותפים לפי הסדר, וקבוצת גיבוב של אחד המערכים מאפשרת לבדוק אם "הערך הזה נמצא ב־nums1?" בזמן קבוע.
השוו כל זוג
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
עבור כל ערך של nums1, סרוק את nums2 כדי למצוא אותו. עצור את הסריקה בהתאמה הראשונה, ודלג על ערך שכבר מופיע בתשובה, כך שהשוואת [8, 8, 8, 8] מול [8, 8] תיתן 8 אחד, ולא ארבעה. מיין את התשובה בסוף.
הפתרון נכון כי ערך נכנס לתשובה בדיוק כשעותק כלשהו שלו ב-nums1 מוצא התאמה ב-nums2, והדילוג מונע ממנו להיכנס פעמיים.
הפתרון איטי כי כל ערך של nums1 עשוי לסרוק את כל nums2. כשיש 5000 ערכים בכל מערך, מדובר בעד 2.5 × 10^7 השוואות, ובבדיקות הגדולות רוב הערכים לא מוצאים התאמה, ולכן רוב הסריקות נמשכות עד הסוף.
אלגוריתם
- התחל עם רשימת תשובות ריקה.
- עבור כל ערך
aב־nums1, דלג עליו אם הוא כבר נמצא בתשובה. - אחרת, סרוק את
nums2; בערך הראשון ששווה ל־a, הוסף אתaלתשובה והפסק את הסריקה. - מיין את התשובה בסדר עולה והחזר אותה.
def intersection(nums1, nums2):
result = []
for a in nums1:
if a in result:
continue
# Look for a anywhere in nums2.
for b in nums2:
if a == b:
result.append(a)
break
result.sort()
return resultמיין את שניהם, ואז עבור באמצעות שני מצביעים
האינטואיציה
לאחר המיון, דוגמה 1 הופכת ל־[2, 2, 4, 6, 9] ול־[1, 4, 4, 6]. הצב את המצביע i בתחילת המערך הראשון ואת j בתחילת המערך השני. המצביע שנמצא על הערך הקטן יותר מתקדם: הערך הזה לא יכול להתאים לשום ערך בהמשך המערך האחר, שבו כל הערכים גדולים ממנו או שווים לו. כששני המצביעים מצביעים על אותו ערך, הוא משותף, ולכן הוסף אותו והזז את שניהם.
בדוגמה: 2 > 1 מזיז את j, שני ערכי ה־2 קטנים מ־4 ומזיזים את i, 4 = 4 מוסיף את 4, ה־4 השני קטן מ־6 ומזיז את j, ו־6 = 6 מוסיף את 6. ערך שמופיע כמה פעמים בשני הצדדים, כמו 2 ב־[2, 2, 3] וב־[2, 2], מתאים יותר מפעם אחת; השוואתו לערך האחרון שנוסף מבטיחה שתישאר עותק אחד. התוצאה מתקבלת ממוינת, בלי שלב נוסף.
המיון עולה O(n log n + m log m), והמעבר עולה O(n + m), כי בכל שלב לפחות מצביע אחד מתקדם. ברוב המימושים ממיינים עותקים, וזה עולה O(n + m) זיכרון. אם מותר לך לשנות את סדר הקלטים, מיין אותם במקום, כפי שעושה קוד C, ואז הזיכרון הנוסף היחיד הוא עבור התשובה.
אלגוריתם
- מיין את שני המערכים.
- הגדר
i = 0ואתj = 0. - כל עוד שני המצביעים נמצאים בתוך המערכים שלהם, הזז את המצביע שנמצא על הערך הקטן יותר.
- כאשר הערכים שווים, הוסף את הערך אלא אם הוא שווה לערך האחרון שנוסף, ואז הזז את שני המצביעים.
- החזר את התשובה.
def intersection(nums1, nums2):
a = sorted(nums1)
b = sorted(nums2)
i, j = 0, 0
result = []
while i < len(a) and j < len(b):
if a[i] < b[j]:
i += 1
elif a[i] > b[j]:
j += 1
else:
# A shared value: keep it once, even if it repeats.
if not result or result[-1] != a[i]:
result.append(a[i])
i += 1
j += 1
return resultקבוצת גיבוב של המערך הראשון
האינטואיציה
מכניסים כל ערך של nums1 לקבוצת גיבוב. בדוגמה 1 הקבוצה היא {6, 2, 9, 4}: הערך 2 שמופיע שוב מתאחד עם הערך הקיים בעת ההכנסה. לאחר מכן עוברים על nums2 ובודקים מול הקבוצה כל ערך בזמן קבוע. ה-4 הראשון נמצא בה, ולכן הוא נכנס לתשובה. ה-4 השני לא צריך להיכנס, ולכן מסירים ערך מהקבוצה ברגע שהוא נמצא בה. 1 לא נמצא בה, ו-6 כן, ולכן מתקבלת התוצאה [4, 6].
ההסרה בעת מציאת התאמה היא זו שמבטיחה שכל ערך יופיע פעם אחת: אחרי ההתאמה הראשונה שלו, הערך יוצא מהקבוצה, ולכן עותקים מאוחרים יותר ב-nums2 לא מוצאים דבר. כל ערך שנוסף מופיע בשני המערכים, וכל ערך משותף מתווסף כשמגיע העותק הראשון שלו ב-nums2.
בניית הקבוצה והמעבר על המערך אורכים בממוצע O(n + m). התשובה מתקבלת לפי הסדר של nums2, ולכן ממיינים אותה בסוף; היא מכילה k ≤ min(n, m) ערכים, והמיון עולה O(k log k). ל-C אין קבוצה מובנית, ולכן קוד ה-C משתמש במערך דגלים שהאינדקסים שלו הם value + 10^5, וזה עובד מכיוון שהערכים מוגבלים.
אלגוריתם
- בנה קבוצת גיבוב
firstמתוךnums1. - עבור כל ערך ב־
nums2, אם הוא נמצא ב־first, הוסף אותו לתשובה והסר אותו מ־first. - מיין את התשובה בסדר עולה.
- החזר אותה.
def intersection(nums1, nums2):
first = set(nums1)
result = []
for num in nums2:
if num in first:
result.append(num)
# Remove it so a repeat in nums2 is not added twice.
first.remove(num)
result.sort()
return result
מלכודות ומקרי קצה
רוב התשובות השגויות כאן נובעות מערכים שחוזרים על עצמם ומסדר הפלט.
- הוספת ערך בכל פעם שהוא תואם.
[2, 2, 3, 3, 3]ו-[3, 2, 2]חולקים שני ערכים, לכן התשובה היא[2, 3], ולא[3, 2, 2]. - החזרת הערכים לפי הסדר שבו מצאת אותם. המעבר על קבוצת הגיבוב עוקב אחר
nums2, לכן עדיין צריך למיין את[7, -3]ל-[-3, 7]. - מיון מספרים כטקסט.
sort()של JavaScript ללא פונקציית השוואה משווה מחרוזות, לכן[100000, 99]נשאר בסדר הזה. יש להעביר את(x, y) => x - y. - שימוש בחיתוך של קבוצות ושכחת הסדר.
set(nums1) & set(nums2)של Python מוצא את הערכים הנכונים בסדר לא מוגדר; יש לעטוף אותו ב-sorted. - שימוש בערך הגולמי כאינדקס במערך דגלים.
-3אינו אינדקס תקף; יש להזיז תחילה כל ערך ב-10^5.
שאלות נפוצות4
מהי סיבוכיות הזמן של חיתוך בין שני מערכים?
בעזרת קבוצת גיבוב, מציאת הערכים המשותפים אורכת בממוצע O(n + m), ומיון k הערכים שבתשובה מוסיף O(k log k); הקבוצה משתמשת בזיכרון בנפח O(n). מיון שני המערכים ומעבר עליהם בעזרת שני מצביעים אורכים O(n log n + m log m). השוואת כל זוג אורכת O(n × m).
האם כדאי להשתמש בקבוצת גיבוב או בשני מצביעים?
השתמשו בקבוצת גיבוב כשהמערכים אינם ממוינים ויש זיכרון פנוי: היא דורשת הכי פחות עבודה. השתמשו בשני מצביעים כשהמערכים כבר ממוינים, או כשהזיכרון מוגבל ואפשר למיין אותם במקום. הסריקה אינה דורשת קבוצה ומפיקה את התשובה לפי הסדר.
איך שומרים ערכים חוזרים בחיתוך?
אם ערך אמור להופיע מספר הפעמים שהוא מופיע בשני המערכים, כך ש־[3, 1, 3, 3] ו־[3, 3] יחזירו [3, 3], החליפו את הקבוצה במפת ספירות. ספרו את הערכים של nums1, ועבור כל ערך של nums2 שהספירה שלו גדולה מאפס, הוסיפו אותו והפחיתו את הספירה שלו. במהלך המעבר עם שני המצביעים, הסירו את הבדיקה מול הערך האחרון שנוסף.
איך מוצאים את החיתוך כאשר מערך אחד גדול מדי מכדי להיכנס לזיכרון?
בנו את קבוצת הגיבוב מתוך המערך שנכנס, וקראו את המערך הגדול בחלקים. בדקו כל ערך מול הקבוצה והסירו אותו כשיש התאמה. הזיכרון נשאר בגודל המערך הקטן יותר. אם אף אחד מהמערכים לא נכנס, מיינו את שניהם בדיסק ובצעו סריקה בשני מצביעים על הקבצים הממוינים.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def intersection(nums1, nums2):
# כתבו כאן קודמקרה 1
מקרה 2
קלט
nums1 = [6, 2, 9, 2, 4] nums2 = [4, 4, 1, 6]
צפוי
[4, 6]