Leaders in an Array

+10

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

الدالة

leaders(nums: integer-array) → integer-array

numsinteger-array: مصفوفة الأعداد الصحيحة المراد البحث فيها
تُرجعinteger-array: العناصر القائدة في nums، من اليسار إلى اليمين

القيود

1 ≤ nums.length ≤ 25000
-10⁹ ≤ nums[i] ≤ 10⁹

أمثلة

المدخلات: nums = [12, 5, 9, 3, 6, 2]
المخرجات: [12, 9, 6, 2]
الشرح: العدد 2 هو الأخير، لذا يتصدر. العدد 6 يتغلب على العدد 2 الذي يليه، والعدد 9 يتغلب على 3 و6 و2، والعدد 12 يتغلب على الجميع. العدد 5 يخسر أمام 9، والعدد 3 يخسر أمام 6، لذا فالإجابة هي [12, 9, 6, 2].

سؤال إضافي

إذا وصلت القيم واحدة تلو الأخرى، وكان عليك بعد كل قيمة الإبلاغ عن القيم المتصدرة حتى الآن، فكيف تحدّث القائمة في زمن O(1) مُستهلك لكل قيمة؟

تلميحات

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

فُتح 0 من 3

الحل

عند القراءة من اليسار، يحتاج كل عنصر إلى فحص جديد للجزء اللاحق منه. تحرّك من اليمين بدلًا من ذلك: كل ما تحتاج إلى معرفته عن الجزء اللاحق هو أكبر قيمة فيه، ويمكن لمتغير واحد أن يحتفظ بها. وهذا يحوّل فحصًا بتعقيد O(n²) إلى مرور واحد.

تحقّق من كل شيء على اليمين

صحيحة، لكنها لا تنتهي في أكبر الاختبارات

الفكرة

طبّق التعريف: لكل فهرس i، افحص العناصر اللاحقة وتوقّف عند أول عنصر أكبر تمامًا من nums[i]. إذا وصل الفحص إلى النهاية، فإن nums[i] يكون قائدًا. اختبر الفهارس من اليسار إلى اليمين، لذا تظهر العناصر القائدة بالترتيب. في [12, 5, 9, 3, 6, 2]، يتوقّف الفحص عند 5 عند الوصول إلى 9، وعند 3 عند الوصول إلى 6.

الخوارزمية

أنشئ قائمة نتائج فارغة.
لكل فهرس i، افحص j من i + 1 حتى النهاية.
إذا كان أيّ من nums[j] أكبر من nums[i]، فتوقّف: nums[i] ليس عنصرًا قائدًا.
إذا لم يوجد j كهذا، فأضف nums[i] إلى النتيجة.
أعِد النتيجة.

def leaders(nums):
    n = len(nums)
    result = []
    for i in range(n):
        is_leader = True
        for j in range(i + 1, n):
            if nums[j] > nums[i]:  # a bigger value on the right rules it out
                is_leader = False
                break
        if is_leader:
            result.append(nums[i])
    return result

مرور واحد من اليمين مع الاحتفاظ بالقيمة القصوى الحالية

الفكرة

كون العنصر أكبر من أو مساويًا لكل عنصر على يمينه يعني الشيء نفسه كونه أكبر من أو مساويًا لأكبرها. وأنت تتحرك من اليمين إلى اليسار، يمكنك تحديث هذه القيمة العظمى باستمرار. يتصدر العنصر الأخير ويبدأ القيمة العظمى. ويتصدر كل عنصر على يساره عندما يكون أكبر من القيمة العظمى أو مساويًا لها، ثم يصبح القيمة العظمى الجديدة؛ وإلا فهناك قيمة أكبر إلى يمينه.

في [12, 5, 9, 3, 6, 2]: يتصدر 2، ثم 6، ثم 9، ثم 12، بينما تكون 3 و5 دون القيمة العظمى. لقد وجدت [2, 6, 9, 12]؛ وعند عكس ترتيبها، تكون هي الإجابة.

تُقارَن العناصر مرة واحدة: زمن O(n) ومساحة إضافية O(1)، باستثناء النتيجة. يضع إصدار R علامات على العناصر المتصدرة في متجه logical(n)، لذا تكون مساحته الإضافية O(n).

الخوارزمية

ضع العنصر الأخير في النتيجة واجعل best يساويه.
حرّك i من الفهرس قبل الأخير نزولًا إلى 0.
إذا كان nums[i] ≥ best، فأضف nums[i] إلى النتيجة واجعل best يساويه.
اعكس النتيجة ليُقرأ القادة من اليسار إلى اليمين، ثم أعدها.

def leaders(nums):
    n = len(nums)
    best = nums[n - 1]  # the largest value to the right of the current index
    found = [best]      # the last element is always a leader
    for i in range(n - 2, -1, -1):
        if nums[i] >= best:
            best = nums[i]
            found.append(nums[i])
    found.reverse()  # collected right to left, returned left to right
    return found

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

استخدام > بدلًا من ≥ عند المقارنة بالحد الأقصى الحالي. في [4, 7, 7, 1, 7]، كل قيمة 7 تُعدّ عنصرًا قائدًا، لكن المقارنة الصارمة لا تحتفظ إلا بالأخيرة.
بدء الحد الأقصى عند 0 بدلًا من العنصر الأخير. يجب أن تُرجع [-1, -5] العنصرين معًا، لكن الحد الأقصى 0 يستبعدهما.
إرجاع العناصر القائدة بالترتيب الذي عثرتَ عليها به، أي [2, 6, 9, 12] بدلًا من [12, 9, 6, 2].
إضافة العنصر الأخير مرتين، وذلك ببدء الحلقة عند الفهرس الأخير بعد إضافته مسبقًا إلى النتيجة.
مقارنة كل عنصر بجاره فقط. في [5, 3, 9]، يتفوّق 5 على 3 المجاور له، لكن وجود 9 يعني أن الإجابة هي [9].

أسئلة شائعة3

ما هو التعقيد الزمني لإيجاد العناصر القائدة في مصفوفة؟

‏O(n) بتمريرة واحدة من اليمين، لأن كل عنصر يُقارَن مرة واحدة بالحد الأقصى الجاري. وتكلفة فحص كل عنصر ومقارنته بكل ما يقع على يمينه هي ‏O(n²)‏ في أسوأ الحالات، مثلًا عندما تكون جميع القيم متساوية.

هل العنصر الأخير دائمًا قائدًا؟

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

هل تُحتسب القيم المتساوية ضمن القيم المتصدرة؟

هنا، نعم: يجب أن يكون العنصر القائد أكبر من أو مساويًا لكل عنصر يقع على يمينه، لذا في [4, 7, 7, 1, 7] تكون قيم 7 الثلاث كلها عناصر قائدة. تشترط بعض الإصدارات أن يكون العنصر أكبر تمامًا؛ عندئذٍ قارن باستخدام >، ولا يكون عنصرًا قائدًا سوى آخر قيمة من القيم المتساوية.

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

اختبار #1

اختبار #2

اختبار #3

وسيط

nums = [12, 5, 9, 3, 6, 2]

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

[12, 9, 6, 2]