Find Peak Element

Q: ما هو التعقيد الزمني لخوارزمية Find Peak Element؟

يعمل البحث الثنائي في زمن O(log n) ومساحة O(1) ، وبحد أقصى 13 خطوة لـ 5000 قيمة. أما السير من اليسار فيستغرق زمن O(n) ، إذ قد يقرأ كل زوج قبل أن يعثر على الانخفاض.

Q: هل يظل البحث الثنائي يعمل عند وجود عدة قمم؟

نعم، ما دامت القيم المتجاورة مختلفة، وتُعدّ المواضع الواقعة بعد الطرفين أقل من كل قيمة. تُرجع هذه الطريقة قمة واحدة، وليس بالضرورة أعلى قمة. بعد خطوة صعود، لا بد أن تبدأ القيم بالانخفاض عند نهاية النطاق على أبعد تقدير، لذا فإن أول انعطاف هو قمة، وبالتالي يحتوي الجانب الذي يواصل البحث فيه دائمًا على قمة واحدة.

Q: هل تكون القمة دائمًا أكبر قيمة؟

في هذه المسألة، نعم: ترتفع المصفوفة حتى تصل إلى قمة واحدة ثم تنخفض بعدها، لذا لا يمكن أن تكون هناك قيمة أخرى أكبر. أما في النسخة التي تحتوي على قمم متعددة، فالأمر ليس كذلك، لأن أي قيمة أكبر من جارتَيها تُعدّ قمة. لهذا السبب تقارن عملية البحث بين العناصر المتجاورة بدلًا من البحث عن القيمة القصوى.

متوسطالبحث الثنائي

+10

تصعد المصفوفة nums ثم تهبط: تكون كل قيمة أكبر من القيمة التي تسبقها حتى فهرسٍ ما، وتكون كل قيمة بعد ذلك الفهرس أصغر من القيمة التي تسبقها. قد يكون أيٌّ من الجزأين فارغًا، لذا قد تصعد المصفوفة فقط أو تهبط فقط. القيمة عند فهرس التحوّل هي القمّة، وهي القيمة الوحيدة الأكبر من جميع جيرانها.

أعِد فهرس القمّة في زمن O(log n).

الدالة

findPeakElement(nums: integer-array) → integer

numsinteger-array: القيم، إذ ترتفع إلى ذروة واحدة ثم تنخفض
تُرجعinteger: فهرس القمة

القيود

1 ≤ nums.length ≤ 5000
-10⁶ ≤ nums[i] ≤ 10⁶
nums[i] != nums[i+1] لكل i صالح.
nums تزداد بصرامة حتى فهرس واحد، ثم تتناقص بصرامة بعده، لذا توجد قمة واحدة بالضبط.

أمثلة

المدخلات: nums = [2, 5, 9, 4, 1]
المخرجات: 2
الشرح: تزداد القيم عبر 2 و5 و9، ثم تنخفض عبر 4 و1. تقع نقطة التحول عند 9، الفهرس 2.

سؤال إضافي

في شبكة لا تتساوى فيها أي خليتين متجاورتين، تكون القمة خلية أكبر من جيرانها الأربعة على الأكثر. هل يمكنك العثور على قمة دون قراءة كل خلية؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

مع وجود قمة واحدة، تكون القمة أكبر قيمة، لذا تعثر عليها عملية مرور واحدة في O(n). ولتحقيق O(log n)، قارِن nums[mid] بـ nums[mid+1]: يخبرك الميل عند mid بأي جانب من القمة يقع، لذا يمكن في كل خطوة استبعاد نصف النطاق.

امشِ حتى تبدأ القيم في الانخفاض

الفكرة

قبل القمة، تكون كل قيمة أصغر من القيمة التي تليها، ومن القمة فصاعدًا تكون كل قيمة أكبر. لذا، تكون القمة أول فهرس i حيث nums[i] > nums[i+1]، أو الفهرس الأخير إذا كان المصفوفة لا تفعل سوى الصعود.

عندما تقع القمة عند نهاية 5000 قيمة، يتطلب المرور 4999 مقارنة، بينما يحتاج البحث الثنائي إلى 13.

الخوارزمية

لكل قيمة من i من 0 إلى n-2، قارِن nums[i] بـ nums[i+1].
عند أول قيمة لـ i يكون فيها nums[i] أكبر، أعد i.
إذا انتهت الحلقة دون انخفاض، فأعد n-1.

def findPeakElement(nums):
    for i in range(len(nums) - 1):
        if nums[i] > nums[i + 1]:
            return i  # the first step down starts at the peak
    return len(nums) - 1  # never went down: the last value is the peak

البحث الثنائي على الميل

الفكرة

اقرأ زوجًا واحدًا، nums[mid] وnums[mid+1]. تعني الخطوة إلى الأعلى أن المصفوفة ما زالت تصعد، وهذا لا يحدث في هذه المصفوفة إلا قبل القمة: تقع القمة عند mid+1 أو إلى يمينه. وتعني الخطوة إلى الأسفل أنك عند القمة أو تجاوزتها: تقع القمة عند mid أو إلى يساره.

احتفظ بنطاق [lo, hi] يحتوي دائمًا على القمة. تنقل الخطوة إلى الأعلى lo إلى mid+1. وتنقل الخطوة إلى الأسفل hi إلى mid، مع الإبقاء على mid لأنه قد يكون القمة. عندما يلتقي lo وhi، يكون الفهرس الوحيد المتبقي هو القمة. إن تقريب mid إلى الأسفل يُبقيه أقل من hi، لذا يكون mid+1 موجودًا دائمًا.

في المثال الأول، عند mid = 2 نرى أن 9 > 4، لذا hi = 2؛ ثم عند mid = 1 نرى أن 5 < 9، لذا lo = 2، وهي القمة. تستغرق 5000 قيمة 13 خطوة على الأكثر.

الخوارزمية

عيّن lo = 0 وhi = n-1.
ما دام lo < hi، احسب mid = lo + (hi - lo) / 2 وقرّب الناتج إلى الأسفل.
إذا كان nums[mid] < nums[mid+1]، فعيّن lo = mid + 1.
وإلا فعيّن hi = mid.
أعِد lo.

def findPeakElement(nums):
    lo, hi = 0, len(nums) - 1  # the peak is always inside [lo, hi]
    while lo < hi:
        mid = lo + (hi - lo) // 2  # mid < hi, so mid + 1 is a valid index
        if nums[mid] < nums[mid + 1]:
            lo = mid + 1  # still climbing: the peak is to the right of mid
        else:
            hi = mid  # going down: the peak is mid or to its left
    return lo

أخطاء شائعة وحالات حدّية

تعيين hi = mid - 1 عند الانتقال إلى خطوة أدنى. في [2, 5, 9, 4, 1] تكون قيمة mid الأولى هي القمة نفسها، وتعيين hi = 1 يستبعدها؛ لذا يُرجع البحث 1.
المقارنة مع nums[mid-1] عند تقريب mid إلى الأسفل. قد تكون قيمة mid هي 0، وعندها لا يوجد عنصر مجاور على اليسار.
استخدام نطاق نصف مفتوح مع hi = n. عندها قد تكون قيمة mid هي n-1، ويقرأ nums[mid+1] خارج نهاية المصفوفة، حتى عند وجود قيمة واحدة فقط.
نسيان الإزاحة في Lua وR. تظل الإجابة هي الفهرس الذي يبدأ من 0، لذا تُعاد قيمة الموضع i على هيئة i-1.

أسئلة شائعة3

ما هو التعقيد الزمني لخوارزمية Find Peak Element؟

يعمل البحث الثنائي في زمن O(log n) ومساحة O(1)، وبحد أقصى 13 خطوة لـ 5000 قيمة. أما السير من اليسار فيستغرق زمن O(n)، إذ قد يقرأ كل زوج قبل أن يعثر على الانخفاض.

هل يظل البحث الثنائي يعمل عند وجود عدة قمم؟

نعم، ما دامت القيم المتجاورة مختلفة، وتُعدّ المواضع الواقعة بعد الطرفين أقل من كل قيمة. تُرجع هذه الطريقة قمة واحدة، وليس بالضرورة أعلى قمة. بعد خطوة صعود، لا بد أن تبدأ القيم بالانخفاض عند نهاية النطاق على أبعد تقدير، لذا فإن أول انعطاف هو قمة، وبالتالي يحتوي الجانب الذي يواصل البحث فيه دائمًا على قمة واحدة.

هل تكون القمة دائمًا أكبر قيمة؟

في هذه المسألة، نعم: ترتفع المصفوفة حتى تصل إلى قمة واحدة ثم تنخفض بعدها، لذا لا يمكن أن تكون هناك قيمة أخرى أكبر. أما في النسخة التي تحتوي على قمم متعددة، فالأمر ليس كذلك، لأن أي قيمة أكبر من جارتَيها تُعدّ قمة. لهذا السبب تقارن عملية البحث بين العناصر المتجاورة بدلًا من البحث عن القيمة القصوى.

def findPeakElement(nums):
    # اكتب الكود هنا

اختبار #1

اختبار #2

اختبار #3

وسيط

nums = [2, 5, 9, 4, 1]

الإخراج المتوقع