Sort List
لديك قائمة مترابطة أحادية مخزنة في مصفوفتين لهما الطول نفسه. تحتوي العقدة i على القيمة values[i] وترتبط بالعقدة next[i]، وتنهي -1 القائمة، ورأس القائمة هو العقدة 0. العقد غير مخزنة بترتيب القائمة، وقد تحتوي المصفوفتان أيضًا على عقد متبقية لا تصل إليها أبدًا عند التتبع بدءًا من العقدة 0. هذه العقد ليست جزءًا من القائمة، حتى عندما تشير روابطها إليها.
رتّب القائمة ترتيبًا غير تنازلي حسب القيمة، وأعِد قيم عقدها بهذا الترتيب.
الدالة
- 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]