Majority Element

+10

لديك مصفوفة من الأعداد الصحيحة nums طولها n. تظهر إحدى القيم فيها أكثر من n / 2 مرة، وتُسمّى هذه القيمة العنصر الغالب. أعد هذه القيمة. لا يمكن أن توجد إلا قيمة واحدة تظهر أكثر من نصف عناصر المصفوفة، لذا توجد إجابة واحدة بالضبط.

الدالة

majorityElement(nums: integer-array) → integer

numsinteger-array: مصفوفة الأعداد الصحيحة، مع قيمة واحدة تملأ أكثر من نصفها
تُرجعinteger: القيمة التي تظهر أكثر من n / 2 مرة

القيود

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
تظهر إحدى القيم أكثر من nums.length / 2 مرة.

أمثلة

المدخلات: nums = [3, 9, 3, 3, 4]
المخرجات: 3
الشرح: يظهر الرقم 3 ثلاث مرات ضمن خمسة عناصر. ثلاثة أكبر من 5 / 2 = 2.5، ويظهر كل من 9 و4 مرة واحدة.

+15 اختبارات مخفية عند الإرسال

سؤال إضافي

هل يمكنك إيجاد العنصر الأكثر تكرارًا في زمن O(n) وبذاكرة إضافية O(1)، دون فرز المصفوفة؟

الحل

إن عدّ عدد مرات ظهور كل قيمة يجيب عن السؤال، لكن هذه الأعداد تتطلب خريطة تجزئة. ويمكن الاستغناء عنها بالنظر إلى ما يميّز قيمة الأغلبية: فهي تتجاوز جميع القيم الأخرى مجتمعةً في عدد مرات الظهور. أقرن كل نسخة منها بقيمة مختلفة واشطب كليهما، وستبقى بعض نسخها دائمًا. تنفّذ خوارزمية التصويت لبويير-مور هذا الاقتران في مرور واحد باستخدام مرشّح واحد وعداد واحد.

العدّ باستخدام خريطة تجزئة

الفكرة

امشِ عبر المصفوفة واحتفظ بخريطة تجزئة تربط كل قيمة بعدد مرات رؤيتك لها. بعد زيادة عدد قيمة بمقدار واحد، تحقّق مما إذا كان هذا العدد قد تجاوز الآن نصف الطول. أول قيمة تتجاوز هذا الحد هي قيمة الأغلبية، لذا يمكنك إرجاعها فورًا.

بالنسبة إلى [3, 9, 3, 3, 4]، يصبح عدد مرات ظهور 3 هو 1 عند الفهرس 0، و2 عند الفهرس 2، و3 عند الفهرس 3. ظهورها ثلاث مرات من أصل خمس أكثر من 2.5، لذا تعيد 3 من دون قراءة العنصر الأخير.

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

الخوارزمية

أنشئ خريطة فارغة من القيم إلى أعداد تكرارها.
لكل عنصر x، أضف 1 إلى عدد مرات ظهور x.
إذا كان هذا العدد مضروبًا في 2 أكبر من طول المصفوفة، فأعِد x.

def majorityElement(nums):
    counts = {}
    for x in nums:
        counts[x] = counts.get(x, 0) + 1
        if counts[x] * 2 > len(nums):
            return x

تصويت بوير-مور

الفكرة

تعامل مع المصفوفة كأنها انتخابات. احتفظ بـ candidate واحد وcount لعدد أصواته التي لم يُلغِها شيء بعد. العنصر المطابق للمرشح يضيف صوتًا. أما العنصر المختلف عنه فيلغي صوتًا، ويغادر العنصران السباق معًا. عندما يصبح العدد 0، يصبح العنصر التالي هو المرشح الجديد.

لماذا تكون القيمة المتبقية في النهاية هي قيمة الأغلبية: كل عملية إلغاء تزيل قيمتين مختلفتين، لذا لا يمكنها إزالة أكثر من نسخة واحدة من قيمة الأغلبية. لنفترض أن الأغلبية تظهر m مرة. لا يوجد سوى n - m من العناصر الأخرى، وهو عدد أقل من m، لذا لا يمكنها إلغاء جميع النسخ. كل صوت يظل قائمًا في النهاية ينتمي إلى المرشح النهائي، ومن بينها نسخة من قيمة الأغلبية، لذا فالمرشح هو قيمة الأغلبية.

في [8, 8, 1, 1, 8, 1, 8] يصبح العدد 1، ثم 2، ثم 1، ثم 0: ألغى العددان 1 كلا نسختي 8. تبدأ نسخة 8 التالية من جديد بعدد 1، وتلغيها نسخة 1 التالية، ثم تصبح نسخة 8 الأخيرة هي المرشح مجددًا. تُرجع 8. مرور واحد باستخدام متغيرين يوفّر زمنًا قدره O(n) وذاكرة قدرها O(1).

الخوارزمية

عيّن candidate ليكون العنصر الأول، وعيّن count إلى 0.
لكل عنصر x، إذا كان count يساوي 0، فاجعل x هو المرشح.
إذا كان x يساوي المرشح، فأضف 1 إلى count. وإلا فاطرح 1.
بعد العنصر الأخير، أعد candidate.

def majorityElement(nums):
    candidate = nums[0]
    count = 0
    for x in nums:
        if count == 0:
            candidate = x  # the old candidate's votes are used up
        if x == candidate:
            count += 1
        else:
            count -= 1  # x and one copy of the candidate cancel out
    return candidate

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

معظم الإجابات الخاطئة تأتي من سوء فهم شرط النصف أو من المبالغة في تفسير العداد.

«أكثر من النصف» شرط صارم. يقبل count >= n / 2 نسختين من أصل 4، وهذا ليس أغلبية. قارِن باستخدام count * 2 > n، وبذلك لا يمكن أن يؤثر التقريب في النتيجة.
القيمة النهائية لـ count في خوارزمية Boyer-Moore لا تمثل عدد مرات ظهور العنصر الأغلبي. بالنسبة إلى [8, 8, 1, 1, 8, 1, 8] تكون قيمتها 1 في النهاية، بينما يظهر 8 أربع مرات.
البدء بـ candidate = nums[0] وcount = 1 ينجح فقط إذا بدأت الحلقة بعد ذلك عند الفهرس 1. إذا بدأت عند الفهرس 0، فسيُحتسب تصويت العنصر الأول مرتين: عند استخدام [1, 2, 2] تصبح قيمة العداد 0، وتُعيد 1.
تعتمد خوارزمية Boyer-Moore على وجود ضمان. ففي [1, 2, 3]، التي لا تحتوي على عنصر أغلبي، تُعيد مع ذلك 3. إذا كان من المحتمل ألا يحتوي الإدخال على عنصر أغلبي، فاحسب عدد مرات ظهور العنصر المرشح في مرورٍ ثانٍ قبل الوثوق به.

أسئلة شائعة4

ما خوارزمية التصويت Boyer-Moore؟

يعثر على القيمة التي تظهر في أكثر من نصف عناصر القائمة في مرور واحد وبذاكرة O(1). يحتفظ بقيمة مرشحة وعداد: يضيف عنصر مطابق واحدًا إلى العداد، ويطرح عنصر مختلف واحدًا منه، وعندما يصل العداد إلى 0 يصبح العنصر التالي هو القيمة المرشحة. وبما أن قيمة الأغلبية تتجاوز مجموع مرات ظهور جميع القيم الأخرى، فهي القيمة المرشحة المتبقية في النهاية.

ما تعقيد الزمن والمساحة لمسألة Majority Element؟

تعمل خوارزمية التصويت Boyer-Moore بزمن O(n) ومساحة إضافية O(1). ويستغرق العد باستخدام خريطة تجزئة أيضًا زمن O(n)، لكنه يحتاج إلى مساحة O(n) لتخزين التكرارات. أما الفرز أولًا فيستغرق زمن O(n log n).

هل يمكن حل مسألة العنصر الأكثر تكرارًا بالفرز؟

نعم. بعد الترتيب، تكون جميع نسخ عنصر الأغلبية متجاورة في كتلة يزيد طولها على نصف المصفوفة، وأي كتلة كهذه تشمل الموضع الأوسط. لذا فإن العنصر عند الفهرس n / 2، بعد التقريب إلى الأسفل، هو الإجابة. يسهل كتابة ذلك، لكنه يستغرق زمنًا قدره O(n log n).

ماذا لو لم يكن من المؤكد أن تحتوي المصفوفة على عنصر أغلبية؟

تعيد خوارزمية Boyer-Moore دائمًا مرشحًا ما، حتى عندما لا توجد قيمة تشغل أكثر من نصف المصفوفة. أضف مرورًا ثانيًا يحصي المرشح، واقبله فقط إذا كان العدد أكبر من n / 2. يظل الإجمالي O(n) من حيث الزمن وO(1) من حيث المساحة.

Python

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

حالات الاختبار

الحالة 1

الحالة 2

المدخلات

nums = [3, 9, 3, 3, 4]

المتوقع