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]