Sort List

+10

נתונה לך רשימה מקושרת חד־כיוונית המאוחסנת בשני מערכים באותו אורך. צומת i מכיל את הערך values[i] ומקושר לצומת next[i], -1 מסיים את הרשימה, והראש הוא צומת 0. הצמתים אינם מאוחסנים לפי סדר הרשימה, והמערכים עשויים להכיל גם צמתים שנותרו, שהמעבר מצומת 0 לעולם אינו מגיע אליהם. צמתים אלה אינם חלק מהרשימה, גם אם הקישורים שלהם מצביעים אליה.

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

פונקציה

sortList(next: integer-array, values: integer-array) → integer-array

nextinteger-array: האינדקס של הצומת שאליו כל צומת מקושר, או -1 עבור הצומת האחרון
valuesinteger-array: הערך שמוחזק בכל צומת
מחזירהinteger-array: הערכים של איברי הרשימה, מהקטן לגדול

אילוצים

1 ≤ n ≤ 4000, כאשר n הוא האורך של next ושל values.
-1000 ≤ values[i] ≤ 1000
כל next[i] הוא -1 או אינדקס של צומת בין 0 ל־n-1.
החל מצומת 0, הרשימה מגיעה אל -1 בלי לבקר באותו צומת פעמיים.
צמתים שהמעבר החל מהצומת 0 אינו מגיע אליהם אינם חלק מהרשימה. הערכים שלהם ב-next יכולים להצביע לכל מקום.

דוגמאות

קלט: next = [3, -1, 4, 2, 1]values = [4, 1, 3, 2, 5]
פלט: [1, 2, 3, 4, 5]
הסבר: ההליכה מהצומת 0 מבקרת בצמתים 0, 3, 2, 4, 1, ולכן הרשימה היא 4, 2, 3, 5, 1. לאחר מיון, מתקבל 1, 2, 3, 4, 5.

קלט: next = [2, 0, -1, -1]values = [6, 9, -2, 5]
פלט: [-2, 6]
הסבר: הרשימה היא 0 → 2, כלומר 6, -2. לא מגיעים לצמתים 1 ו-3 מהראש, ולכן הערכים שלהם 9 ו-5 נשארים בחוץ, אף שצומת 1 מקושר לצומת 0.

קלט: next = [1, 2, 3, -1]values = [3, -1, 3, -1]
פלט: [-1, -1, 3, 3]
הסבר: הרשימה נקראת 3, -1, 3, -1. ערכים שווים נשארים בתשובה כמספר הפעמים שהם מופיעים: -1, -1, 3, 3.

שאלת המשך

האם תוכל למיין על ידי קישור מחדש של הצמתים בזמן O(n log n), בלי להעתיק את הערכים החוצה?

פתרון

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

העתק את הערכים למערך ומיין אותו

האינטואיציה

הרשימה היא כל מה שהמעבר node = next[node] מבקר בו, החל מהצומת 0 ועד -1. אספו את הערכים האלה במערך חדש, מיינו אותו באמצעות פעולת המיון המובנית והחזירו אותו. אי אפשר למיין ישירות את values: בדוגמה השנייה הוא מכיל את 9 ואת 5, שאינם נמצאים ברשימה.

המעבר הוא בסיבוכיות O(n) והמיון בסיבוכיות O(n log n), עם זיכרון נוסף בסיבוכיות O(n). הרשימה עצמה לעולם אינה משתנה, ולכן מראיינים מבקשים את הגישה הבאה.

אלגוריתם

התחל עם מערך ריק ועם node = 0.
כל עוד node אינו -1, הוסף את values[node] ועבור אל next[node].
מיין את המערך בסדר עולה והחזר אותו.

def sortList(next, values):
    # Collect the values of the nodes on the list, then sort them.
    on_list = []
    node = 0
    while node != -1:
        on_list.append(values[node])
        node = next[node]
    on_list.sort()
    return on_list

מיון מיזוג של הקישורים

האינטואיציה

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

בדוגמה הראשונה, slow נעצר על 3, וניתוק החוליה שלו מפצל את 4, 2, 3, 5, 1 ל-4, 2, 3 ול-5, 1. אלה ממוינים ל-2, 3, 4 ול-1, 5, והמיזוג לוקח את 1, 2, 3, 4, ואז מקשר את 5 שנותר.

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

אלגוריתם

אם ברשימה יש צומת אחד (next[head] == -1), החזר את head.
הגדר slow = head ואת fast = next[head]; התקדם עם slow קישור אחד ועם fast שני קישורים, כל עוד fast ו-next[fast] אינם -1.
הגדר second = next[slow] ונתק באמצעות next[slow] = -1.
מיין את שני החצאים באופן רקורסיבי. מזג אותם: קשר את הצומת הקדמי הקטן יותר אחרי tail עד שאחד החצאים מתרוקן, ואז קשר את שארית החצי השני.
עבור מהראש שהוחזר ואסוף את הערכים.

def sortList(next, values):
    def merge(a, b):
        # Splice two sorted lists into one; on a tie the node from a goes first.
        head = tail = -1
        while a != -1 and b != -1:
            if values[b] < values[a]:
                node, b = b, next[b]
            else:
                node, a = a, next[a]
            if tail == -1:
                head = node
            else:
                next[tail] = node
            tail = node
        next[tail] = a if a != -1 else b  # attach whatever is left
        return head

    def sort(head):
        if next[head] == -1:  # one node is already sorted
            return head
        # slow stops on the last node of the first half
        slow, fast = head, next[head]
        while fast != -1 and next[fast] != -1:
            slow = next[slow]
            fast = next[next[fast]]
        second = next[slow]
        next[slow] = -1  # cut the list in two
        return merge(sort(head), sort(second))

    result = []
    node = sort(0)
    while node != -1:
        result.append(values[node])
        node = next[node]
    return result

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

מיון כל המערך values. בדוגמה השנייה, שמכניסה את 9 ואת 5, שאינם מופיעים ברשימה.
התחלת fast בראש הרשימה. כשיש שני צמתים, slow מגיע אז לצומת השני, החיתוך משאיר חצי שני ריק, והרקורסיה לא מצמצמת את הרשימה.
שכחת החיתוך next[slow] = -1. כך החצי הראשון ממשיך אל החצי השני, ושתי הקריאות ממיינות רשימות חופפות.
השמטת שארית של חצי כשנגמר החצי השני. הצמתים האלה נעלמים מהתוצאה.
ב-Lua וב-R, המערכים מתחילים ב-1: השאר את האינדקסים של הצמתים מבוססי 0 וקרא את next[node + 1]. גרסת R מעתיקה את מערך הקישורים פעם אחת, ולכן היא משתמשת בזיכרון נוסף של O(n).

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

מהי הדרך הטובה ביותר למיין רשימה מקושרת?

מיון מיזוג. פיצול באמצע, מיון שני החצאים ומיזוגם — כל אלה מתקדמים לאורך הרשימה, הכיוון היחיד שנתמך ברשימה מקושרת חד־כיוונית. זמן הריצה הוא O(n log n), והפעולה מקשרת מחדש את הצמתים הקיימים.

למה מיון מיזוג מועדף על פני מיון מהיר עבור רשימות מקושרות?

Quicksort יכול לחלק רשימה באמצעות קישור מחדש, אבל ציר טוב דורש גישה אקראית, ובחירת הראש כציר גורמת לרשימה ממוינת לעלות O(n²). Merge sort תמיד מחלק לשניים, ולכן נשאר O(n log n) בכל קלט.

האם ניתן למיין רשימה מקושרת בזמן של O(n log n) ובזיכרון של O(1)?

כן, באמצעות מיון מיזוג מלמטה למעלה. הוא ממזג רצפים שכנים באורך 1, אחר כך באורך 2, ואז באורך 4, עד שרצף אחד מכסה את הרשימה. יש log n מעברים ליניאריים, והזיכרון היחיד שנדרש הוא כמה אינדקסים של צמתים.

def sortList(next, values):
    # כתבו כאן קוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנטים

next = [3, -1, 4, 2, 1]
values = [4, 1, 3, 2, 5]

הפלט הצפוי

[1, 2, 3, 4, 5]