Find Minimum in Rotated Sorted Array
قائمة من الأعداد الصحيحة المتميزة رُتبت بترتيب تصاعدي ثم دُوّرت: أُخذ عدد من العناصر، قد يكون صفرًا، من البداية ونُقلت إلى النهاية بالترتيب نفسه. على سبيل المثال، تدوير [2, 5, 9, 11, 13, 15, 17] بمقدار 3 يعطي [11, 13, 15, 17, 2, 5, 9]. تحصل على القائمة المدورة nums. أعد أصغر قيمة فيها في زمن O(log n).
الدالة
- numsinteger-array
- القائمة المُدوَّرة المرتبة من أعداد صحيحة متميزة
- تُرجعinteger
- أصغر قيمة في nums
القيود
1 ≤ nums.length ≤ 5000-104 ≤ nums[i] ≤ 104- جميع القيم في
numsمختلفة. numsهي قائمة متزايدة دُوِّرت بمقدار ماkحيث0 ≤ k < nums.length؛ وتبقى دون تدوير عندما تكونk = 0.
أمثلة
- المدخلات
- nums = [11, 13, 15, 17, 2, 5, 9]
- المخرجات
- 2
- الشرح
- ترتفع القيم من 11 إلى 17 ثم تنخفض إلى 2، حيث يبدأ التكرار الثاني. ترى عملية البحث أن 17 > 9 عند الفهرس 3، لذا فإن القيمة الدنيا تقع إلى يمينه؛ ثم تؤدي 5 ≤ 9 و2 ≤ 5 إلى إرجاع
hiإلى الخلف حتى يصبح النطاق مقتصرًا على الفهرس 4، الذي يحتوي على 2.
- المدخلات
- nums = [4, 7, 10, 12]
- المخرجات
- 4
- الشرح
- دُوِّرت هذه القائمة بمقدار 0، لذا لا تزال مرتبة، وأصغر قيمة فيها هي قيمتها الأولى. كل قيمة وسطية أقل من القيمة الأخيرة أو تساويها، لذا يستمر
hiفي التحرك إلى اليسار حتى يصل إلى الفهرس 0، الذي يحتوي على 4.
- المدخلات
- nums = [30, -6, 0, 8, 19]
- المخرجات
- -6
- الشرح
- نُقلت أربع قيم من المقدمة إلى النهاية، لذا أصبحت القيمة الأكبر، 30، في البداية، وأصبح الحد الأدنى، -6، عند الفهرس 1. يضيّق البحث النطاق إلى الفهرسين 0 و1، ويرى أن 30 > -6، وينقل
loإلى 1.
+17 اختبارات مخفية عند الإرسال
سؤال إضافي
هل يمكنك إرجاع القيمة الأصغر ذات الترتيب k في nums خلال زمن O(log n)، من دون ترتيبها؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
في قائمة مرتبة، تكون كل قيمة أكبر من القيمة التي تسبقها. ويكسر التدوير هذا الترتيب في موضع واحد بالضبط. أين تقع أصغر قيمة بالنسبة إلى ذلك الموضع؟
قارن القيمة الوسطى بآخر قيمة في نطاقك. إذا كانت القيمة الوسطى أكبر، فلا بد أن تنخفض القيم في موضع ما بعدها. وإذا كانت أصغر، فإن الجزء الممتد من الوسط إلى النهاية يرتفع دون أي انخفاض.
أبقِ
loوhiحول الحد الأدنى. عندما يكونnums[mid] > nums[hi]، حرّكloإلىmid + 1؛ وإلا فحرّكhiإلىmid، لأنmidنفسه قد يكون الحد الأدنى. توقّف عندما يتساوىloوhi.
الحل
القائمة المرتبة بعد تدويرها تتكوّن من مقطعين متزايدين، [11, 13, 15, 17] ثم [2, 5, 9]. الحد الأدنى هو أول قيمة في المقطع الثاني، مباشرةً بعد الموضع الوحيد الذي تنخفض فيه القيم. يحدّد المرور على القائمة هذا الانخفاض في O(n). تخبرك مقارنة قيمة وسطية بآخر قيمة في النطاق بأي جانب من موضع الانخفاض تقع القيمة الوسطية، لذا يعثر عليه البحث الثنائي في O(log n).
استمر حتى تنخفض القيم
الفكرة
في القائمة المرتبة، تكون كل قيمة أكبر من القيمة التي تسبقها. يحافظ تدوير القائمة على ترتيب كلا الجزأين، وينشئ موضعًا واحدًا فقط يختل فيه ذلك: حيث تأتي أصغر قيمة بعد أكبر قيمة. لذا مرّ على القائمة من اليسار إلى اليمين، وأعِد أول قيمة أصغر من جارتها على اليسار. إذا لم توجد قيمة كهذه، فهذا يعني أن القائمة دُوّرت بمقدار 0، وأن القيمة الصغرى هي nums[0].
في [11, 13, 15, 17, 2, 5, 9]، يتجاوز المرور القيم 13 و15 و17، وكل منها أكبر من القيمة التي تسبقها، ثم يتوقف عند الفهرس 4، حيث إن 2 أصغر من 17. وهذا أفضل بالفعل من إيجاد أصغر قيمة بين جميع العناصر، لأنه يتوقف عند موضع الانخفاض، لكن موضع الانخفاض قد يكون في أي مكان. عندما ينقل التدوير عنصرًا واحدًا، كما في [2, 3, 4, 5, 6, 7, 8, 1]، يقرأ المرور القائمة بأكملها: 5000 مقارنة لـ 5000 عنصر، بينما يحتاج البحث الثنائي إلى 13 مقارنة.
الخوارزمية
- لكل فهرس
iمن 1 إلىn-1، قارنnums[i]معnums[i-1]. - إذا كان
nums[i] < nums[i-1]، فأعِدnums[i]: يبدأ الجزء المرتب الثاني هناك. - إذا انتهت الحلقة، فهذا يعني أن القائمة لم تُدَر: أعِد
nums[0].
def findMin(nums):
for i in range(1, len(nums)):
if nums[i] < nums[i - 1]:
return nums[i] # the only drop: the second run starts here
return nums[0] # no drop: the list was not rotatedالبحث الثنائي عن القيمة الأخيرة
الفكرة
التزم بوعد واحد: الحد الأدنى يقع بين lo وhi، شاملًا الطرفين. في البداية، يكون هذا النطاق هو القائمة بأكملها. انظر إلى القيمة الوسطى وقارنها بـnums[hi]، وهي القيمة الأخيرة في النطاق.
إذا كانت nums[mid] > nums[hi]، فإن القيم تنخفض في موضع ما بين mid وhi، والحد الأدنى هو القيمة الواقعة مباشرة بعد ذلك الانخفاض، أي إلى يمين mid: عيّن lo = mid + 1. وإلا، تكون nums[mid] < nums[hi] (فالقيم مختلفة)، لذا فإن nums[mid..hi] تزداد دون أي انخفاض فيها. عندئذٍ يكون الحد الأدنى هو nums[mid] أو قيمة تسبقها، لذا عيّن hi = mid. لا تتجاوز mid: فقد تكون هي الحد الأدنى. كل حركة من الحركتين تحافظ على الوعد وتقلّص النطاق، وعندما يصل lo إلى hi تكون القيمة الوحيدة المتبقية هي الحد الأدنى.
تتبّع المثال الأول، [11, 13, 15, 17, 2, 5, 9]. النطاق من 0 إلى 6 له منتصف عند 3، وقيمته 17، وهي أكبر من nums[6] = 9، لذا تصبح lo مساويةً لـ4. النطاق من 4 إلى 6 له منتصف عند 5، وقيمته 5، وهي ليست أكبر من 9، لذا تصبح hi مساويةً لـ5. النطاق من 4 إلى 5 له منتصف عند 4، وقيمته 2، وهي ليست أكبر من 5، لذا تصبح hi مساويةً لـ4. أعد nums[4] = 2.
تُقلّص كل خطوة النطاق إلى النصف، لذا تتكرر الحلقة نحو log2(n) مرة كحد أقصى: 13 خطوة لـ5000 عنصر، مع استخدام فهرسين من الذاكرة الإضافية.
الخوارزمية
- عيّن
lo = 0وhi = n-1. - ما دام
lo < hi، احسبmid = lo + (hi - lo) / 2. - إذا كان
nums[mid] > nums[hi]، فعيّنlo = mid + 1. - وإلا فعيّن
hi = mid. - عند انتهاء الحلقة، أعد
nums[lo].
def findMin(nums):
lo, hi = 0, len(nums) - 1 # the minimum sits in nums[lo..hi]
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] > nums[hi]:
lo = mid + 1 # the values drop after mid, so the minimum is right of it
else:
hi = mid # nums[mid..hi] climbs: the minimum is at mid or left of it
return nums[lo]
أخطاء شائعة وحالات حدّية
تتكوّن الحلقة من أربعة أسطر، ولكل سطر نسخة خاطئة مغرية.
- كتابة
hi = mid - 1في الفرع الثاني. يُنفَّذ هذا الفرع عندما يكون من الممكن أن تكونmidهي القيمة الصغرى نفسها. في[3, 1, 2]، القيمة الوسطى 1 ليست أكبر من 2، لذا تصبحhiمساوية لـ 0 وتُرجع الدالة 3. - التكرار باستخدام
lo ≤ hi. عندما تصبحloمساوية لـhi، تصبحmidمساوية لكليهما، وتكونnums[mid] > nums[hi]خاطئة، ولا يغيّرhi = midشيئًا: فلا تنتهي الحلقة أبدًا. توقّف عندما يتبقى عنصر واحد في النطاق، باستخدامlo < hi. - المقارنة مع
nums[lo]بدلًا منnums[hi]. في القائمة غير المدارة[1, 2, 3, 4, 5]، تكون القيمة الوسطى 3 أكبر منnums[0] = 1، ما يوحي بأن نقطة الانخفاض تقع إلى اليمين، لذا يتحرك البحث مبتعدًا عن القيمة الصغرى الحقيقية عند الفهرس 0 ويُرجع 4. - إرجاع
loبدلًا منnums[lo]. المطلوب هو القيمة؛ أما الفهرس فهو إجابة عن سؤال مختلف (راجع الأسئلة الشائعة حول عدد مرات التدوير). - افتراض أن القائمة قد دُوّرت. يُسمح بالتدوير بمقدار 0، وأي كود يبحث عن نقطة انخفاض من دون معالجة بديلة قد يقرأ خارج حدود القائمة أو لا يُرجع شيئًا. أرجِع
nums[0]إذا لم توجد نقطة انخفاض.
أسئلة شائعة4
ما هو التعقيد الزمني لإيجاد أصغر عنصر في مصفوفة مرتبة ومدوّرة؟
زمن O(log n) ومساحة إضافية O(1) باستخدام البحث الثنائي. في كل خطوة، نحتفظ بنصف النطاق، لذا تحتاج قائمة تضم 5000 عنصر إلى 13 مقارنة على الأكثر. المسح بحثًا عن موضع الانخفاض يستغرق O(n): إذ يقرأ كل عنصر عندما تكون القيمة الصغرى في النهاية.
لماذا نقارن nums[mid] بـ nums[hi] وليس بـ nums[lo]؟
لأن nums[hi] يحدد دائمًا أي جانب يقع فيه الحد الأدنى، بينما لا يفعل nums[lo] ذلك. إذا كان nums[mid] > nums[hi]، فلا بد أن تقع القيم بين mid وhi؛ وإلا فإن nums[mid..hi] تزداد، ويكون الحد الأدنى عند mid أو قبله. أما مع nums[lo]، فإن النتيجة nums[mid] > nums[lo] تنطبق على كلٍّ من القائمة غير المدارة، حيث يكون الحد الأدنى هو nums[lo]، والقائمة المدارة، حيث يقع إلى يمين mid.
كيف تعرف عدد مرات تدوير مصفوفة مرتبة؟
نفّذ البحث الثنائي نفسه وأعِد lo، وهو فهرس أصغر قيمة، بدلًا من nums[lo]. إذا اعتبرتَ التدوير نقل العنصر الأخير إلى المقدمة، فإن هذا الفهرس هو عدد مرات التدوير. أما إذا اعتبرتَه نقل العنصر الأول إلى النهاية، كما تفعل هذه المسألة، فالعدد هو (n - lo) mod n: في [11, 13, 15, 17, 2, 5, 9] تقع أصغر قيمة عند الفهرس 4، وطرح 4 من 7 يعطي القيم الثلاث المنقولة.
هل يعمل البحث الثنائي عندما تحتوي المصفوفة على عناصر مكررة؟
ليس دون تغيير. في [2, 2, 2, 0, 2]، يمكن أن تكون nums[mid] مساوية لـ nums[hi]، وعندها لا يمكن استبعاد أيٍّ من الجانبين. إن تقليص النطاق باستخدام hi = hi - 1 في هذه الحالة آمن، لأن نسخة من nums[hi] تظل ضمن النطاق عند mid، لكن قائمة من القيم المتساوية تتخللها قيمة أصغر مخفية تستغرق بعد ذلك O(n).
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def findMin(nums):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
nums = [11, 13, 15, 17, 2, 5, 9]
المتوقع
2