عنصر اکثریت

دستورالعمل‌ها

به شما این وظیفه سپرده شده است که تشخیص دهید آیا در یک کیسه، رنگ آب‌نباتی وجود دارد که سهم اکثریت کیسه را تشکیل می‌دهد. 🍬 «عنصر اکثریت» عنصری است که بیش از نیمی از فضای یک مجموعه را اشغال می‌کند. با گرفتن لیستی از عناصر که رنگ‌ها را نشان می‌دهند، رنگی را که به‌عنوان اکثریت یافت شده است برگردانید؛ در غیر این صورت نشان دهید که هیچ اکثریتی یافت نشده است.

برای یک لیست ساده، [Red, Red, Blue, Red, Green]، مقدار برگردانده‌شده باید Red باشد چون Red در لیستی با ۵ عنصر ۳ بار ظاهر می‌شود. اما برای لیست [Red, Red, Blue, Green]، هیچ اکثریتی وجود ندارد، با اینکه Red رایج‌ترین عنصر است، چون ۲/۴ از نیمی از عناصر بیشتر نیست.

پیاده‌سازی

• امتیاز: آیا می‌توانید پیاده‌سازی‌تان را طوری تعمیم دهید که عنصر اکثریت را در هر نوعی از List پیدا کند؟
• امتیاز: اگر برای یافتن عنصر اکثریت، عنصرهای متفاوت زیادی برای انتخاب وجود داشته باشد، آیا پیاده‌سازی‌تان کارآمد است؟
• هرچند می‌توانید تابع majorityFinder را به هر روشی که می‌خواهید پیاده‌سازی کنید، ما چند استاب فراهم کرده‌ایم که از توانایی MyStore استفاده می‌کنند. (توانایی MyStore همان Store در کتابخانه‌ی استاندارد است، اما اینجا برای رفع ابهام اسم کمی متفاوتی به آن داده‌ایم.) اگر بخواهید از این توانایی استفاده کنید، باید هندلر runWith را پیاده‌سازی کنید. runWith هم نتیجه‌ی اجرای تابعی را که از توانایی MyStore استفاده می‌کند برمی‌گرداند و هم وضعیت نهایی MyStore را.
• برای اطلاعات بیشتر درباره‌ی اینکه هندلرهای توانایی چطور وضعیت را ردیابی می‌کنند، مستندات هندلر توانایی را بخوانید.

---

منبع

Boyer Moore Majority Vote Algorithm