Merge Two Sorted Lists

Q: מהי סיבוכיות הזמן של מיזוג שתי רשימות ממוינות?

זהו O(L1 + L2) : כל השוואה ממקמת צומת אחד, ואף צומת אינו ממוקם פעמיים. עם אובייקטים של צמתים, המיזוג דורש O(1) זיכרון נוסף, מכיוון שהוא רק משנה קישורים. עם המערכים שבהם משתמשים כאן, מערך הקישורים המשותף דורש O(L1 + L2) זיכרון.

קלרשימה מקושרת שני מצביעים

+10

נתונות לך שתי רשימות מקושרות חד־כיווניות, שכל אחת מהן שמורה בשני מערכים בעלי אותו אורך. ברשימה הראשונה, הצומת i מכיל את הערך values1[i] ומקושר לצומת next1[i]. הרשימה השנייה פועלת באותו אופן, עם next2 ו-values2. בשתי הרשימות -1 מסמן את סוף הרשימה, והראש הוא הצומת 0. הצמתים אינם שמורים לפי סדר הרשימה, לכן יש לעקוב אחר הקישורים.

כל רשימה ממוינת בסדר לא יורד לאורך הקישורים שלה. מזגו את השתיים לרשימה ממוינת אחת והחזירו את הערכים שלה לפי הסדר.

פונקציה

mergeTwoLists(next1: integer-array, values1: integer-array, next2: integer-array, values2: integer-array) → integer-array

next1integer-array: האינדקס של הצומת שאליו מקושר כל צומת ברשימה הראשונה, או ‎-1‎ עבור הצומת האחרון שלה
values1integer-array: הערך שמחזיקה כל צומת ברשימה הראשונה
next2integer-array: האינדקס של הצומת שאליו מקושר כל צומת ברשימה השנייה, או ‎-1 עבור הצומת האחרון שלה
values2integer-array: הערך שמוחזק בכל צומת ברשימה השנייה
מחזירהinteger-array: הערכים של הרשימה הממוזגת, לפי הסדר

אילוצים

1 ≤ L1 ≤ 2000, כאשר L1 הוא האורך של next1 ושל values1.
1 ≤ L2 ≤ 2000, כאשר L2 הוא האורך של next2 ושל values2.
-1000 ≤ values1[i], values2[j] ≤ 1000
כל איבר ב־next1 הוא -1 או אינדקס של צומת ברשימה הראשונה, וכל איבר ב־next2 הוא -1 או אינדקס של צומת ברשימה השנייה.
החל מהצומת 0, כל אחת מהרשימות מבקרת בכל אחד מהצמתים שלה בדיוק פעם אחת ואז מגיעה ל־-1. אין מחזור.
לאורך הקישורים שלה, כל רשימה ממוינת בסדר שאינו יורד.

דוגמאות

קלט: next1 = [2, -1, 1]values1 = [1, 6, 4]next2 = [3, 2, -1, 1]values2 = [2, 7, 9, 3]
פלט: [1, 2, 3, 4, 6, 7, 9]
הסבר: במעקב אחר הקישורים, הרשימה הראשונה מבקרת בצמתים 0, 2, 1 וקוראת את 1, 4, 6; השנייה קוראת את 2, 3, 7, 9. בחירה בכל פעם בערך הקטן יותר מבין האיברים הראשונים נותנת את 1, 2, 3, 4, 6, 7, 9.

קלט: next1 = [2, -1, 1]values1 = [-3, 5, 0]next2 = [-1]values2 = [0]
פלט: [-3, 0, 0, 5]
הסבר: הרשימה הראשונה כוללת את הערכים -3, 0, 5 והשנייה היא הערך היחיד 0. שני הערכים 0 נשארים בתוצאה, ולכן יש בה ארבעה ערכים.

קלט: next1 = [1, -1]values1 = [8, 10]next2 = [2, -1, 1]values2 = [1, 3, 2]
פלט: [1, 2, 3, 8, 10]
הסבר: הרשימה השנייה נקראת 1, 2, 3, כולם קטנים מ־8 שמתחיל את הרשימה הראשונה. כל הרשימה השנייה מופיעה קודם, ואז 8, 10.

שאלת המשך

האם תוכל למזג k רשימות ממוינות בזמן O(N log k), כאשר N הוא המספר הכולל של הצמתים?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

שתי הרשימות ממוינות, לכן הערך הקטן ביותר שנותר תמיד נמצא בתחילתה של אחת מהן. השווה בין שני הערכים הראשונים, קשר את הקטן יותר לתוצאה והתקדם ברשימה הזו. מיון כל N = L1 + L2 הערכים גם עובד, אבל הוא מתעלם מהסדר הזה ועולה O(N log N).

שים כל ערך במערך אחד ומיין אותו

האינטואיציה

הרשימה הממוזגת היא הגרסה הממוינת של כל הערכים N, לכן העתיקו את שני מערכי הערכים לאחד ומיינו אותו. הסדר של הצמתים בתוך המערכים לא משנה, כי המיון מציב כל ערך. עם N ≤ 4000 זה מהיר מספיק, אבל מיון עולה O(N log N) השוואות, בעוד שמיזוג דורש לכל היותר N-1, והוא אף פעם לא נוגע בקישור — המיומנות שהבעיה הזו בודקת.

אלגוריתם

העתק את values1 ואת values2 למערך אחד.
מיין את המערך בסדר לא יורד.
החזר אותו.

def mergeTwoLists(next1, values1, next2, values2):
    # Sorting puts every value in its place without following a single link.
    return sorted(values1 + values2)

שרשר את הצמתים אחרי ראש דמה

האינטואיציה

מצביע כאן הוא אינדקס של צומת. כדי לקשר את הצמתים של שתי הרשימות לשרשרת אחת, נותנים להם מספור אחד: צומת j ברשימה 2 הופך לצומת L1+j, והקישורים שלו מוזזים באותו אופן. צומת דמה, שמספרו L1+L2, מוצב לפני התוצאה.

משאירים את a ואת b על הצומת הראשון שעדיין לא נוצל בכל רשימה, ואת tail בסוף השרשרת הממוזגת. בכל צעד מקשרים את tail לחזית הקטנה יותר ומקדמים את המצביע הזה ואת tail. כאשר אחת הרשימות נגמרת, שאר הצמתים של הרשימה האחרת כבר ממוינים ומקושרים, ולכן השמה אחת מחברת אותם. בדוגמה הראשונה, רשימה 2 הופכת לצמתים 3 עד 6. אחרי הצמתים 0, 3, 6, 2, 1, רשימה 1 ריקה, ו-link[tail] = 4 מחבר את 7, 9.

כל צומת מקושר לכל היותר פעם אחת: זמן O(N). מערך הקישורים המשותף צורך זיכרון O(N), בעוד שאובייקטי צומת לא היו דורשים זיכרון נוסף.

אלגוריתם

בנו מערך קישורים אחד: next1, ואז next2 מוזז ב-L1 (השאירו את -1 ללא שינוי), ואז -1 עבור L1+L2 הדמה. בנו את הערכים התואמים.
הגדירו את a = 0, את b = L1 ואת tail כמצביע לצומת הדמה.
כל עוד לא a ולא b הם -1, קשרו את tail לקטן מביניהם (במקרה של שוויון, a), התקדמו עם המצביע הזה והעבירו את tail אליו.
קשרו את tail לזה מבין a ו-b שאינו -1.
עברו מ-link[dummy] עד -1 ואספו את הערכים.

def mergeTwoLists(next1, values1, next2, values2):
    n1 = len(next1)
    n2 = len(next2)
    # One node space: list 2's node j becomes node n1 + j, and node n1 + n2 is a
    # dummy that sits in front of the merged list.
    link = list(next1) + [j + n1 if j != -1 else -1 for j in next2] + [-1]
    value = list(values1) + list(values2)
    dummy = n1 + n2
    tail = dummy  # the last node of the merged list so far
    a = 0  # the first unused node of list 1
    b = n1  # the first unused node of list 2
    while a != -1 and b != -1:
        if value[a] <= value[b]:
            link[tail] = a  # splice a in after the tail
            a = link[a]
        else:
            link[tail] = b  # splice b in after the tail
            b = link[b]
        tail = link[tail]
    # One list ran out. The rest of the other one is sorted and linked already.
    link[tail] = a if a != -1 else b
    merged = []
    node = link[dummy]
    while node != -1:
        merged.append(value[node])
        node = link[node]
    return merged

מלכודות ומקרי קצה

מיזוג המערכים לפי סדר האינדקסים. הצמתים מאוחסנים בסדר מעורבב, ולכן values1 עצמו אינו ממוין: בדוגמה הראשונה הוא [1, 6, 4]. רק ההליכה מהצומת 0 ממוינת.
שכחת הערכים שנותרו. כשהרשימה אחת נגמרת, הלולאה נעצרת, והשמטת שאר הרשימה האחרת גורמת לאובדן הערכים הגדולים ביותר: 7, 9 בדוגמה הראשונה.
קידום המצביע הלא נכון, או קידום של שניהם. רק הרשימה שממנה לקחת צומת מתקדמת.
ערבוב בין שתי שיטות המספור. צומת 2 ברשימה 2 אינו צומת 2 ברשימה 1. יש להזיז את האינדקסים והקישורים של רשימה 2 ב-L1, ולהשאיר את -1 כפי שהוא.

שאלות נפוצות3

מהי סיבוכיות הזמן של מיזוג שתי רשימות ממוינות?

זהו O(L1 + L2): כל השוואה ממקמת צומת אחד, ואף צומת אינו ממוקם פעמיים. עם אובייקטים של צמתים, המיזוג דורש O(1) זיכרון נוסף, מכיוון שהוא רק משנה קישורים. עם המערכים שבהם משתמשים כאן, מערך הקישורים המשותף דורש O(L1 + L2) זיכרון.

למה להשתמש בצומת דמה כשממזגים רשימות מקושרות?

בלעדיו, הצומת הראשון בתוצאה דורש קוד נפרד, כי עדיין אין זנב שאפשר לקשר אותו אחריו. צומת הדמה הוא ראש מציין מקום, ולכן הצומת הראשון מקושר באותו אופן כמו כל צומת אחר. בסוף מחזירים את הצומת הבא של צומת הדמה, ומציין המקום נעלם.

האם כדאי למזג שתי רשימות ממוינות באופן רקורסיבי או איטרטיבי?

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

def mergeTwoLists(next1, values1, next2, values2):
    # כתבו כאן קוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנטים

next1 = [2, -1, 1]
values1 = [1, 6, 4]
next2 = [3, 2, -1, 1]
values2 = [2, 7, 9, 3]

הפלט הצפוי

[1, 2, 3, 4, 6, 7, 9]