Majority Element

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

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

سهلالتجزئة

+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 مرة واحدة.

سؤال إضافي

هل يمكنك العثور على كل قيمة تظهر أكثر من n / 3 مرة، في زمن O(n) وبذاكرة إضافية O(1)؟

الحل

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

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

الفكرة

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

يستغرق كل بحث 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 الأخيرة المرشّح مرة أخرى. تمريرة واحدة بمتغيرين تستغرق 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 النهائية هي تكرار العنصر ذي الأغلبية. في [8, 8, 1, 1, 8, 1, 8] تنتهي قيمته عند 1، بينما يظهر العدد 8 أربع مرات.
البدء بـ candidate = nums[0] وcount = 1، ثم التكرار بدءًا من الفهرس 0. يصوّت العنصر الأول مرتين: ففي [1, 2, 2] تنتهي قيمة العداد عند 0، وتُرجع 1.

أسئلة شائعة3

ما هو التعقيد الزمني وتعقيد المساحة لعنصر الأغلبية؟

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

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

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

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

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

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

اختبار #1

اختبار #2

وسيط

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

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