Merge Sorted Array
מקבלים שני מערכים של מספרים שלמים, nums1 ו־nums2. כל אחד מהם כבר ממוין בסדר לא יורד. יש להחזיר מערך יחיד שמכיל את כל הערכים משניהם, גם הוא בסדר לא יורד. ערך שמופיע בשני המערכים יופיע בתוצאה כמספר הפעמים שהוא מופיע בסך הכול.
פונקציה
- nums1integer-array
- המערך הממוין הראשון
- nums2integer-array
- המערך הממוין השני
- מחזירהinteger-array
- כל הערכים של שני המערכים במערך ממוין אחד, באורך nums1.length + nums2.length
אילוצים
1 ≤ nums1.length, nums2.length ≤ 2000-105 ≤ nums1[i], nums2[j] ≤ 105nums1ו־nums2ממוינים כל אחד בסדר לא יורד.
דוגמאות
- קלט
- nums1 = [1, 4, 9]nums2 = [2, 3, 10]
- פלט
- [1, 2, 3, 4, 9, 10]
- הסבר
- קרא את שני האיברים הראשונים ושמור את הקטן יותר: 1, ואז 2 ו-3 מתוך
nums2, ואז 4 ו-9 מתוךnums1, ולבסוף 10. התוצאה מכילה את כל ששת הערכים.
- קלט
- nums1 = [-5, 0, 0, 8]nums2 = [0, 6]
- פלט
- [-5, 0, 0, 0, 6, 8]
- הסבר
- ה־0 מופיע פעמיים ב־
nums1ופעם אחת ב־nums2, ולכן בתוצאה יש שלושה 0ים. ה־5- קטן מכל הערכים ב־nums2ומופיע ראשון.
- קלט
- nums1 = [7]nums2 = [3]
- פלט
- [3, 7]
- הסבר
- כל מערך מכיל ערך אחד. 3 קטן מ־7, לכן הוא מופיע ראשון.
+13 בדיקות נסתרות בשליחה
שאלת המשך
האם תוכל למזג k מערכים ממוינים, המכילים בסך הכול N ערכים, בזמן O(N log k)?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
שני המערכים כבר ממוינים. היכן אפשר למצוא את הערך הקטן ביותר בתוצאה כולה?
הערך הקטן ביותר שנותר נמצא תמיד בתחילת
nums1או בתחילתnums2. שמרו אינדקס אחד לכל מערך כדי לסמן את המיקום של כל אחד מהראשים.השווה בין שני האיברים הראשונים, הוסף את הקטן יותר וקדם את האינדקס שלו. כשאחד המערכים מסתיים, שאר המערך השני כבר מסודר, אז הוסף אותו כפי שהוא.
פתרון
חיבור המערכים יחד ומיונם נותנים את התשובה הנכונה, אבל כך מתעלמים מהעובדה ששני החצאים כבר ממוינים. הערך הקטן ביותר שנותר בסך הכול נמצא תמיד בתחילתו של אחד משני המערכים. שמרו אינדקס אחד לכל מערך, בחרו בכל צעד את הערך הקטן יותר מבין הערכים הראשונים, ובמעבר אחד בונים את התוצאה. זהו שלב המיזוג של מיון מיזוג.
שרשר ומיין
האינטואיציה
הכניסו כל ערך של nums1 וכל ערך של nums2 למערך אחד, ואז מיינו אותו. התוצאה מכילה את הערכים הנכונים, כל אחד כמספר הפעמים שבו הוא הופיע, בסדר הנכון.
עבור [1, 4, 9] ו-[2, 3, 10], המערך המשולב הוא [1, 4, 9, 2, 3, 10], והמיון נותן [1, 2, 3, 4, 9, 10].
כאשר יש m ערכים ב-nums1 ו-n ב-nums2, מיון כללי עולה O((m + n) log(m + n)). הוא עובד, והוא מהיר מספיק עבור המגבלות האלה, אבל הוא לא מנצל את הסדר הממויין שניתן לכם. הגישה הבאה כן מנצלת אותו, ומסירה את גורם ה-log.
אלגוריתם
- צרו מערך עם הערכים של
nums1ואחריהם הערכים שלnums2. - מיינו אותו בסדר מספרי עולה.
- החזירו אותו.
def merge(nums1, nums2):
return sorted(nums1 + nums2)שני מצביעים, אחד לכל מערך
האינטואיציה
שמרו אינדקס i בתוך nums1 ואינדקס j בתוך nums2, כששניהם מתחילים ב־0. כל מה שלפני i וכל מה שלפני j כבר נמצא בתוצאה. הערך הקטן ביותר שעדיין לא נעשה בו שימוש הוא nums1[i] או nums2[j], כי כל מערך ממוין והערכים שנותרו בו יכולים להיות גדולים יותר בלבד. הוסיפו את הקטן מביניהם והזיזו את האינדקס המתאים.
עבור [1, 4, 9] ו־[2, 3, 10]: 1 גובר על 2, אחר כך 2 גובר על 4, 3 גובר על 4, 4 גובר על 10, ו־9 גובר על 10. כעת כל הערכים ב־nums1 נוצלו, ולכן שאר הערכים ב־nums2, שהם [10], מועתקים כפי שהם. התוצאה היא [1, 2, 3, 4, 9, 10].
בכל צעד נכתב ערך אחד, ולכן הלולאה רצה m + n פעמים: זמן של O(m + n). מערך התוצאה הוא הזיכרון הנוסף היחיד.
אלגוריתם
- הגדר את
iואתjל־0 וצור תוצאה ריקה. - כל עוד נותרו איברים בשני המערכים, השווה בין
nums1[i]לביןnums2[j]. - הוסף את הקטן מביניהם וקדם את האינדקס שלו. במקרה של שוויון, בחר ב־
nums1[i]. - כשאחד המערכים מתרוקן, הוסף את מה שנותר במערך השני.
- החזר את התוצאה.
def merge(nums1, nums2):
result = []
i = j = 0
while i < len(nums1) and j < len(nums2):
if nums1[i] <= nums2[j]:
result.append(nums1[i])
i += 1
else:
result.append(nums2[j])
j += 1
# one array is used up; the rest of the other is already sorted
result.extend(nums1[i:])
result.extend(nums2[j:])
return result
מלכודות ומקרי קצה
רוב הבאגים מופיעים ברגע שאחד המערכים נגמר, או באופן שבו משווים בין ערכים.
- עצירה של הלולאה ברגע שאחד המערכים נוצל עד תום ושכחה של שאר האיברים במערך האחר. עם
[1, 2, 3]ועם[4, 5, 6], הלולאה מסתיימת אחרי 1, 2 ו-3, ועדיין צריך להעתיק את 4, 5 ו-6. - קריאה של
nums1[i]אחרי ש-iהגיע לסוף. בדקו את שני האינדקסים לפני ההשוואה. - השמטת ערכים כפולים. המיזוג של
[0, 0]ו-[0]יוצר את[0, 0, 0], ולא את[0]. - ב-JavaScript וב-TypeScript, הפונקציה
sort()ללא פונקציית השוואה ממיינת מספרים כטקסט, ולכן[-5, 10, 9]ממוין כך:[-5, 10, 9]. העבירו את(a, b) => a - b. - ב-Lua וב-R, המערכים מתחילים ב-1, ולכן שני האינדקסים מתחילים ב-1 והתנאים לגבולות משתמשים ב-
<=.
שאלות נפוצות4
מהי סיבוכיות הזמן של מיזוג שני מערכים ממוינים?
עם שני מצביעים, הסיבוכיות היא O(m + n), כאשר m ו-n הם שני האורכים. בכל צעד ממקמים ערך אחד, ולא מסתכלים על שום ערך פעמיים. שרשור ומיון עולים O((m + n) log(m + n)) במקום זאת.
איך ממזגים שני מערכים ממוינים במקום?
כאשר יש במערך הראשון מקום לשניהם בסופו, מלא אותו מהסוף. השווה בין הערכים הגדולים ביותר שנותרו בשני המערכים, כתוב את הגדול יותר במשבצת הפנויה האחרונה והתקדם שמאלה. כתיבה מהסוף לעולם אינה דורסת ערך במערך הראשון שעדיין לא הוצב, ולכן אין צורך במערך שני.
האם מיזוג של שני מערכים ממוינים זהה לשלב המיזוג של מיון מיזוג?
כן. מיון מיזוג מחלק מערך לחצאים, ממיין כל חצי ואז מחבר את שני החצאים הממוינים בדיוק באמצעות לולאת שני המצביעים הזאת. בחירה בערך השמאלי במקרה של שוויון שומרת על הסדר המקורי של ערכים שווים, וזה מה שהופך את מיון המיזוג ליציב.
למה לא לשרשר את המערכים ולקרוא ל־sort?
הוא מחזיר את התשובה הנכונה, ובפועל הוא לרוב מהיר. אבל הוא מתעלם מכך שהקלטים כבר ממוינים, וכרוך בעלות של גורם log נוסף. בריאיון מצפים לתשובת המיזוג באמצעות שני מצביעים, כי היא מראה שאפשר לנצל את הסדר שניתן לך.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def merge(nums1, nums2):
# כתבו כאן את הקודמקרה 1
מקרה 2
מקרה 3
קלט
nums1 = [1, 4, 9] nums2 = [2, 3, 10]
צפוי
[1, 2, 3, 4, 9, 10]