Merge Sorted Array
لديك مصفوفتان من الأعداد الصحيحة، nums1 وnums2. كلتاهما مرتبة مسبقًا بترتيب غير تنازلي. أعد مصفوفة واحدة تضم كل القيم من كلتا المصفوفتين، مرتبة أيضًا بترتيب غير تنازلي. تظهر القيمة الموجودة في كلتا المصفوفتين في الناتج بعدد مرات ظهورها الإجمالي.
الدالة
- nums1integer-array
- المصفوفة المرتبة الأولى
- nums2integer-array
- المصفوفة المرتبة الثانية
- تُرجعinteger-array
- جميع قيم المصفوفتين في مصفوفة واحدة مرتبة، بطول يساوي nums1.length + nums2.length
القيود
1 ≤ nums1.length, nums2.length ≤ 2000-105 ≤ nums1[i], nums2[j] ≤ 105- تم ترتيب كلٍّ من
nums1وnums2بترتيب غير تنازلي.
أمثلة
- المدخلات
- nums1 = [1, 4, 9]nums2 = [2, 3, 10]
- المخرجات
- [1, 2, 3, 4, 9, 10]
- الشرح
- اقرأ العنصرين في المقدمة واحتفظ بالأصغر: 1، ثم 2 و3 من
nums2، ثم 4 و9 منnums1، وأخيرًا 10. تحتوي النتيجة على القيم الست كلها.
- المدخلات
- nums1 = [-5, 0, 0, 8]nums2 = [0, 6]
- المخرجات
- [-5, 0, 0, 0, 6, 8]
- الشرح
- يظهر 0 مرتين في
nums1ومرة واحدة فيnums2، لذا تحتوي النتيجة على ثلاثة أصفار. العدد -5 أصغر من كل ما فيnums2ويأتي أولًا.
- المدخلات
- nums1 = [7]nums2 = [3]
- المخرجات
- [3, 7]
- الشرح
- تحتوي كل مصفوفة على قيمة واحدة. 3 أصغر من 7، لذا تأتي أولًا.
+13 اختبارات مخفية عند الإرسال
سؤال إضافي
هل يمكنك دمج k مصفوفات مرتبة، تحتوي على N قيمة إجمالًا، في زمن O(N log k)؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
المصفوفتان مرتبتان بالفعل. أين يمكن العثور على أصغر قيمة في النتيجة بأكملها؟
تكون أصغر قيمة متبقية دائمًا في بداية
nums1أو في بدايةnums2. احتفظ بفهرس لكل مصفوفة لتحديد موضع بدايتها.قارن بين العنصرين الأولين، وألحِق الأصغر منهما ثم حرّك ذلك المؤشر إلى الأمام. عندما تنفد إحدى المصفوفتين، تكون بقية الأخرى مرتبة بالفعل، لذا ألحِقها كما هي.
الحل
يؤدي دمج المصفوفتين معًا وفرزهما إلى الإجابة الصحيحة، لكنه يهدر حقيقة أن كلا النصفين مرتبان بالفعل. أصغر قيمة متبقية إجمالًا تكون دائمًا في مقدمة إحدى المصفوفتين. احتفظ بمؤشر لكل مصفوفة، وخذ القيمة الأصغر من المقدمتين في كل خطوة، وبتمريرة واحدة تُنشئ النتيجة. هذه هي خطوة الدمج في فرز الدمج.
ضمّ ورتّب
الفكرة
ضع كل قيمة من nums1 وكل قيمة من nums2 في مصفوفة واحدة، ثم رتّبها. ستحتوي النتيجة على القيم الصحيحة، كلٌّ منها بعدد مرات ظهوره، وبالترتيب الصحيح.
بالنسبة إلى [1, 4, 9] و[2, 3, 10]، تكون المصفوفة المدمجة هي [1, 4, 9, 2, 3, 10]، ويعطي الترتيب [1, 2, 3, 4, 9, 10].
إذا كان في nums1 عدد m من القيم، وفي nums2 عدد n منها، فإن تكلفة الترتيب العام هي O((m + n) log(m + n)). تنجح هذه الطريقة، وهي سريعة بما يكفي لهذه الحدود، لكنها لا تستفيد من الترتيب المسبق الذي أُعطي لك. أما الطريقة التالية فتستفيد منه، وتزيل عامل log.
الخوارزمية
- أنشئ مصفوفة تحتوي على قيم
nums1متبوعة بقيمnums2. - رتّبها ترتيبًا عدديًا تصاعديًا.
- أعِدها.
def merge(nums1, nums2):
return sorted(nums1 + nums2)مؤشران، واحد لكل مصفوفة
الفكرة
احتفِظ بمؤشر i داخل nums1 ومؤشر j داخل nums2، ويبدأ كلاهما عند 0. كل ما يقع قبل i وقبل j موجود بالفعل في النتيجة. أصغر قيمة لم تُستخدم بعد هي nums1[i] أو nums2[j]، لأن كل مصفوفة مرتبة، ولا يمكن أن تكون القيم المتبقية فيها إلا أكبر. ألحِق الأصغر منهما وحرّك ذلك المؤشر.
في [1, 4, 9] و[2, 3, 10]: يتغلب 1 على 2، ثم يتغلب 2 على 4، و3 على 4، و4 على 10، و9 على 10. الآن استُنفدت nums1، لذا يُنسخ باقي nums2، وهو [10]، كما هو. النتيجة هي [1, 2, 3, 4, 9, 10].
تكتب كل خطوة قيمة واحدة، لذا تتكرر الحلقة m + n مرة: زمن O(m + n). مصفوفة النتيجة هي الذاكرة الإضافية الوحيدة.
الخوارزمية
- اضبط
iوjعلى 0 وأنشئ نتيجة فارغة. - ما دامت هناك قيم متبقية في كلتا المصفوفتين، فقارن
nums1[i]معnums2[j]. - أضف الأصغر منهما وحرّك فهرسه إلى الأمام. عند التعادل، اختر
nums1[i]. - عندما تنفد إحدى المصفوفتين، أضف ما تبقى من الأخرى.
- أعِد النتيجة.
def merge(nums1, nums2):
result = []
i = j = 0
while i < len(nums1) and j < len(nums2):
if nums1[i] <= nums2[j]:
result.append(nums1[i])
i += 1
else:
result.append(nums2[j])
j += 1
# one array is used up; the rest of the other is already sorted
result.extend(nums1[i:])
result.extend(nums2[j:])
return result
أخطاء شائعة وحالات حدّية
تظهر معظم الأخطاء البرمجية عند نفاد أحد المصفوفتين، أو في طريقة مقارنة القيم.
- إيقاف الحلقة بمجرد استنفاد إحدى المصفوفتين ونسيان بقية عناصر الأخرى. مع
[1, 2, 3]و[4, 5, 6]، تنتهي الحلقة بعد 1 و2 و3، ولا يزال يتعين نسخ 4 و5 و6. - قراءة
nums1[i]بعد وصولiإلى النهاية. تحقّق من كلا الفهرسين قبل المقارنة. - إسقاط القيم المكررة. تندمج
[0, 0]و[0]لتصبح[0, 0, 0]، وليس[0]. - في JavaScript وTypeScript، ترتّب
sort()الأرقام كنصوص عند عدم تمرير دالة مقارنة، لذا تُرتّب[-5, 10, 9]لتصبح[-5, 10, 9]. مرّر(a, b) => a - b. - في Lua وR، تبدأ المصفوفات من 1، لذا يبدأ كلا الفهرسين من 1 وتستخدم الحدود
<=.
أسئلة شائعة4
ما هو التعقيد الزمني لدمج مصفوفتين مرتبتين؟
باستخدام مؤشرين، يكون التعقيد O(m + n)، حيث إن m وn هما الطولان. في كل خطوة، توضع قيمة واحدة، ولا يُنظر إلى أي قيمة مرتين. أما الدمج والفرز فيكلفان O((m + n) log(m + n)).
كيف تدمج مصفوفتين مرتبتين في مكانهما؟
عندما تتّسع المصفوفة الأولى لكليهما في نهايتها، املأها بدءًا من الخلف. قارن أكبر القيم المتبقية في المصفوفتين، واكتب الأكبر منها في آخر خانة شاغرة، ثم تحرّك خطوة إلى اليسار. لا تؤدي الكتابة من الخلف إلى استبدال قيمة في المصفوفة الأولى لم توضع بعد، لذا لا حاجة إلى مصفوفة ثانية.
هل دمج مصفوفتين مرتبتين هو نفسه خطوة الدمج في الترتيب بالدمج؟
نعم. يقسم فرز الدمج المصفوفة إلى نصفين، ويرتب كل نصف، ثم يدمج النصفين المرتبين باستخدام حلقة المؤشرين هذه بالضبط. يؤدي أخذ القيمة اليسرى عند التعادل إلى إبقاء القيم المتساوية بترتيبها الأصلي، وهذا ما يجعل فرز الدمج مستقرًا.
لماذا لا ندمج المصفوفتين ونستدعي sort؟
يعطي الإجابة الصحيحة، وغالبًا ما يكون سريعًا في الممارسة. لكنه يتجاهل أن المدخلات مرتبة بالفعل، ويتطلب عاملًا إضافيًا مقداره log. في المقابلة، يُتوقع أن تكون إجابة الدمج باستخدام مؤشرين، لأنها تُظهر قدرتك على الاستفادة من الترتيب المُعطى لك.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def merge(nums1, nums2):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
nums1 = [1, 4, 9] nums2 = [2, 3, 10]
المتوقع
[1, 2, 3, 4, 9, 10]