Merge k Sorted Lists
تحصل على k قوائم من الأعداد الصحيحة بوصفها صفوفًا في lists. كل صف مرتب ترتيبًا غير تنازلي، وقد تختلف أطوال الصفوف، ولا يوجد أي صف فارغ.
ادمجها في قائمة واحدة تضم كل القيم من جميع الصفوف، مرتبة ترتيبًا غير تنازلي، ثم أعدها. تظهر القيمة التي تتكرر عدة مرات، في صف واحد أو في عدة صفوف، بهذا العدد من المرات في النتيجة.
الدالة
- listsinteger-2d-array
- القوائم المرتبة، قائمة واحدة في كل صف، وقد تكون بأطوال مختلفة
- تُرجعinteger-array
- كل قيمة من كل صف، في قائمة واحدة مرتبة
القيود
1 ≤ lists.length ≤ 1041 ≤ lists[i].length، وتحتوي جميع الصفوف معًا على104قيمة كحد أقصى-104 ≤ lists[i][j] ≤ 104- كل صف مرتب ترتيبًا غير تنازلي.
أمثلة
- المدخلات
- lists = [[2, 6, 9], [1, 4, 10], [3, 5]]
- المخرجات
- [1, 2, 3, 4, 5, 6, 9, 10]
- الشرح
- تبدأ الصفوف بـ 2 و1 و3، لذا يأتي 1 أولًا. ثم تكون الرؤوس 2 و4 و3، لذا يأتي 2 بعد ذلك، وهكذا. ينفد الصف الثالث بعد 5، تاركًا 6 و9 و10.
- المدخلات
- lists = [[5], [-2, 5, 7], [0, 5]]
- المخرجات
- [-2, 0, 5, 5, 5, 7]
- الشرح
- تأتي الأعداد 5 الثلاثة من ثلاثة صفوف مختلفة، وتبقى جميعها. يُرتَّب العدد السالب
-2قبل0.
- المدخلات
- lists = [[4, 8]]
- المخرجات
- [4, 8]
- الشرح
- عندما يكون هناك صف واحد، فلا يوجد شيء لدمجه: فالصف مرتب بالفعل، لذا فهو الإجابة.
سؤال إضافي
اعثر على أصغر نطاق [a, b] يحتوي على قيمة من كل صف. هل يمكن استخدام كومة لرؤوس الصفوف بالإضافة إلى أكبر رأس لتحقيق ذلك في O(N log k)؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
كل صف مرتب. ما القيم التي يمكن أن تكون الأصغر على الإطلاق؟
القيمة التالية للإجابة هي دائمًا أصغر قيمة من بين أولى القيم غير المستخدمة في الصفوف. بعد أن تأخذها، تتغير قيمة واحدة فقط من تلك القيم.
احتفِظ بأول قيمة غير مستخدمة من كل صف في كومة صغرى، مع وسم كل قيمة بالصف الذي تنتمي إليه. أزل أصغر قيمة، وألحِقها، ثم أضف القيمة التالية من الصف نفسه إن وُجدت.
الحل
كل صف مرتب، لذا فإن أصغر قيمة غير مستخدمة تكون دائمًا أول قيمة غير مستخدمة في أحد الصفوف، أي رأسه. يتطلب فحص جميع الرؤوس k k خطوات لكل واحدة من القيم N. وتُخرج كومة صغرى للرؤوس أصغر قيمة في O(log k)، مما يخفض الإجمالي من O(N·k) إلى O(N log k).
قارن جميع الرؤوس k لكل قيمة
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
احتفظ بمؤشر pos[r] عند رأس كل صف. في كل جولة، اقرأ رؤوس جميع الصفوف، وأضف أصغر قيمة، ثم حرّك مؤشر ذلك الصف إلى الأمام: هذه هي خطوة الدمج في الترتيب بالدمج، بعد توسيعها من قائمتين إلى k قوائم. في المثال الأول، تكون الرؤوس في البداية 2 و1 و3، لذا تُخرج القيمة 1 ويصبح رأس الصف الثاني 4.
تتطلب كل قيمة من قيم N المرور على جميع الصفوف وعددها k. ومع وجود 10^4 صف، في كل منها قيمة واحدة، فهذا يعني إجراء 10^8 فحصًا للصفوف.
الخوارزمية
- اضبط
pos[r] = 0لكل صف، وعدّ القيم لتحصل علىN. - كرّر ذلك
Nمرة: انظر إلى كل صف لا تزالpos[r]ضمنه، وتذكّر الصف الذي يكون رأسه الأصغر. - أضف ذلك الرأس إلى النتيجة، وزِد
posفي ذلك الصف بمقدار 1. - أعِد النتيجة.
def mergeKLists(lists):
pos = [0] * len(lists) # pos[r]: index of the first unused value in row r
total = sum(len(row) for row in lists)
merged = []
for _ in range(total):
best = -1 # the row whose head is the smallest so far
for r in range(len(lists)):
if pos[r] < len(lists[r]) and (best == -1 or lists[r][pos[r]] < lists[best][pos[best]]):
best = r
merged.append(lists[best][pos[best]])
pos[best] += 1
return mergedكومة صغرى للرؤوس k
الفكرة
بعد كل اختيار يتغير رأس واحد فقط، ومع ذلك تعيد عملية المسح قراءة كل عناصر k. تحتفظ كومة صغرى بالرؤوس، بحيث يكون أصغرها في الأعلى. اربط كل رأس بصفه، حتى تعرف بعد إخراج (value, row) قيمة الصف التالية التي يجب إدراجها. تحتوي الكومة دائمًا على عنصر واحد لكل صف ما دامت فيه قيم متبقية، لذا يكون أصغر قيمة غير مستخدمة في أعلاها.
في المثال الأول، تبدأ الكومة بالقيم 2 و1 و3. أخرج 1 وأدرج 4. أخرج 2 وأدرج 6. أخرج 3 وأدرج 5. أخرج 4 وأدرج 10. أخرج 5: انتهت قيم الصف الثالث، لذا لا يُدرج شيء. أخرج 6 وأدرج 9، ثم أخرج 9 و10.
تُدرج كل قيمة وتُخرج مرة واحدة، ولا تحتوي الكومة مطلقًا على أكثر من k عناصر: 2N عملية، بتعقيد O(log k). عندما يكون N = k = 10^4، يكون العدد أقل من 3 × 10^5 خطوة. تستهلك الكومة ذاكرة مقدارها O(k).
الخوارزمية
- أضِف
(lists[r][0], r)لكل صفrإلى كومة صغرى مرتبة حسب القيمة. - ما دامت الكومة غير فارغة، أخرج أصغر زوج
(value, r)وألحِقvalueبالنتيجة. - إذا كان للصف
rقيمة تالية، فأضِفها معr. - أعِد النتيجة عندما تصبح الكومة فارغة.
import heapq
def mergeKLists(lists):
# The heap holds one (value, row) pair per row that still has values: that row's head.
heap = [(row[0], r) for r, row in enumerate(lists)]
heapq.heapify(heap)
nxt = [1] * len(lists) # nxt[r]: index of row r's next value, not yet in the heap
merged = []
while heap:
value, r = heapq.heappop(heap) # the smallest head of all rows
merged.append(value)
if nxt[r] < len(lists[r]):
heapq.heappush(heap, (lists[r][nxt[r]], r)) # row r's new head takes its place
nxt[r] += 1
return merged
أخطاء شائعة وحالات حدّية
- إدراج القيم وحدها. بعد تنفيذ
pop، لا يمكنك معرفة أي صف يجب الانتقال إليه. خزّن الصف مع القيمة. - استخدام كومة عظمى عن طريق الخطأ. تضع
priority_queueفي C++ وBinaryHeapفي Rust القيمة الأكبر في الأعلى؛ استخدمgreater<>أوReverse. - إدراج كل القيم في البداية. ستظل النتيجة مرتبة، لكن الكومة ستكبر حتى تضم
Nمدخلة، وسيصبح مقدار العملO(N log N). - القراءة بعد نهاية صف قصير. في المثال الأول، يحتوي الصف الثالث على قيمتين، لذا تحقّق من وجود قيمة تالية قبل إدراجها.
- إسقاط القيم المكررة. القيم الخمس 5 في المثال الثاني قيم منفصلة، ويجب أن تظهر كلها في النتيجة.
أسئلة شائعة3
ما هو التعقيد الزمني لدمج قوائم مرتبة عددها k؟
باستخدام كومة صغرى، يكون التعقيد O(N log k)، حيث تمثل N العدد الإجمالي للقيم، ويمثل k عدد القوائم. تُضاف كل قيمة إلى الكومة وتُزال منها مرة واحدة، ولا تحتوي الكومة على أكثر من k مدخلات. تبلغ الذاكرة الإضافية O(k)، بخلاف مساحة الإخراج.
لماذا لا نضع جميع القيم معًا ثم نرتبها؟
هذا صحيح ويستغرق زمنًا قدره O(N log N). يتجاهل أن القوائم مرتبة بالفعل، لذا يدفع تكلفة log N لكل قيمة، بينما تدفع الكومة log k، كما أنه يحتاج إلى وجود جميع القيم في الذاكرة في الوقت نفسه. ويمكن للكومة أيضًا دمج القوائم التي تصل على شكل تدفقات.
هل يمكنك دمج قوائم مرتبة تصاعديًا دون استخدام كومة؟
نعم، باستخدام أسلوب «فرّق تسد». ادمج القوائم على شكل أزواج باستخدام دمج قائمتين، ثم ادمج النتائج على شكل أزواج، وهكذا: log k جولات تلامس كل قيمة مرة واحدة، لذا يكون التعقيد O(N log k). أما دمج القوائم واحدة تلو الأخرى في نتيجة متنامية فهو أبطأ، O(N·k)، لأن القيم المبكرة تُنسخ مجددًا في كل عملية دمج.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def mergeKLists(lists):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
وسيط
lists = [[2, 6, 9], [1, 4, 10], [3, 5]]
الإخراج المتوقع
[1, 2, 3, 4, 5, 6, 9, 10]