المطلوب
الحصول على العنصر الغالب فى قائمة من العناصر ويقال ان العنصر هو العنصر الغالب اذا تكرر العنصر اكثر من نصف طول قائمة العناصر
بمعنى انه اذا احتوت القائمة على n من العناصر فإن العنصر الغالب يجب ان يتكرر اكثر n/2 من المرات
مثال
[my_list = [1,2,2,4,2,2,4,2,6,2
فى المثال السابق عدد العناصر n فى الlist هو 10 وعدد مرات تكرار العنصر 2 هو 6 مرات اي اكبر من n/2
اليك الخوارزميات :
- الطريقة الاولى (Basic algoirthm)
الطريقة الاساسية هى عمل اثنين loop و عد وجود كل العناصر والخروج من loop عند يكون عدد وجود العنصر اكبر من n/ 2
الكود بلغة python
def find_majority_item(my_list):
for x in my_list:
counter = 0
for y in my_list:
if x == y:
counter+=1
if counter > len(my_list)/2:
return x
return False
time complexity = o (n^2)
ملحوظة هذه الطريقة سيئة لأن زمن التنفيذ لها كبير
- الطريقة الثانية وهى الافضل بإستخدام (Moore’s Voting Algorithm)
يقوم algorithm بايجاد عنصر الاغلبية عن طريق تكراره اكثر من نص عدد العناصر الداخلة
العناصر على المحور الافقى هى العناصر الداخلة والارقام على المحور الرأسي هو عدد مرات دخول العنصر(counter) والعنصر على الرسم البيانى هو عنصر الاغلبية المفترض
فى الرسمة السابقة سيعتبر algorithm ان اول عنصر فى المصفوفة هو عنصر الاغلبية وكلما تشابه العنصر التالى مع عنصر الاغلبية المفترض يزيد يزيد عدد مرات حدوث العنصر ولنرمز له ب (counter) كما هو موضح على المحور الافقى و فى حالة عدم تشابه عنصر الاغلبية المفترض مع العنصر الداخل تاليًا فيقل عدد مرات حدوث عنصر الاغلبية (counter) المفترض سابقًا وهكذا يزيد عدد مرات counter للعنصر كلما تشابه مع العنصر الداخل ويقال كلما اختلف عنه فاذا وصل للنهاية ولم يصل counter الى صفر يعتبر هذا عنصر الاغلبية واذا وصل الى الصفر فى اي مرحلة فعتبر العنصر الجديد هو عنصر الاغلبية وهكذا
والسؤال هنا لماذا عند الوصول الى الصفر فقط يتم تغير عنصر الاغلبية القديم الى عنصر جديد ؟
لان معنى الوصل الى الصفر ان عدد مرات حدوث عنصر الاغلبية المفترض تساوي عدد العناصر المختلفة الداخلة فبالتالى لا يوجد عنصر اغلبية فى هذا الجزء لانه كما ذكرنا سابقًا العنصر يعتبر عنصر اغلبية فقط عندما يكون عدد مرات تكراره اكثر النصف
وبالتالى algorithm يبدء فى فرض عنصر اغلبية من جديد لان الفترة السابقة غير مؤثرة
مثال
على فرض المصفوفة
A[] = 2, 2, 3, 5, 2, 2, 6
بالمرور على عناصر المصفوفة عن طريق Loop وفرض العنصر الحالى فى Loop هو number
- على فرض عنصر الاغلبية المفترض او (candidate) هو رقم 2 العنصر الاول و عدد مرات حدوثه او (counter) هى مرة واحدة
- عندما تتحرك اللوب الى العنصر التالى فى المصفوفة وهو 2 ايضًا نجد انه يساوي العنصر ال candidate بالتالى يزيد counter الى 2
- عندما تتحرك اللوب الى العنصر التالى فى المصفوفة وهو 3 نجد ان العنصر لايساوي العنصر ال candidate بالتالى يقل counter الى 1
- عندما تتحرك اللوب الى العنصر التالى فى المصفوفة وهو 5 نجد ان العنصر لايساوي العنصر ال candidate
- بالتالى يقل counter الى 0
- عندما يصل counter الى صفر معنى ذلك انه يمكن تجاهل الفترة السابقة من 2 الى 5 لانها لا تحتوي عنصر عدد مرات تكراره اكبر من طول نصف هذه الفترة وهى 2
- فنبدء من جديد بفرض العنصر الحالى فى اللوب وهو 2 انه عنصر اغلبية وعدد مرات حدوث هو مرة واحدة نفس الشرط رقم واحد
- وعندما تتحرك اللوب الى العنصر التالى وهو 2 نجد ان العنصر يساوي العنصر ال candidate بالتالى يزيد counter الى 2
- وعندما تتحرب اللوب الى العنصر التالى وهو 6 نجد ان العنصر لا يساوي العنصر ال candidate
- بالتالى يقل counter الى 1
- واخيرًا نجد ان candidate هو العنصر 2
الكود بلغة python
def majority_element(seq, default=None):
"""Find which element in *seq* sequence is in the majority.
Return *default* if no such element exists.
Use Moore’s linear time constant space majority vote algorithm
“””
candidate = default
count = 0
for e in seq:
if count != 0:
count += 1 if candidate == e else -1
else: # count == 0
candidate = e
count = 1
# check the majority
return candidate if seq.count(candidate) > len(seq) // 2 else default
time complexity = o (n)
بالتالى هو افضل من حيث الاداء من البرنامج الاول
