الگونَوَردی ۷ (حل شد): یافتن عناصر اکثریت!

اگر نمی دانید که الگونوردی چیست، از این لینک بخوانید.

دسترسی و حل سوال از منبع اصلی

پرسش: یک آرایه به طول N از اعداد صحیح داده شده است. همه عناصری را بیابید که بیش از [n/3] بار تکرار شده اند.

مثال: برای آرایه [3, 2, 3] خروجی [3] می باشد. اگر ورودی [2,2,2,3,3,1,1,1] باشد پاسخ [2,1] می باشد.

توجه کنید که الگوریتم باید خطی باشد و پیچیدگی فضا (O(1.

توجه توجه: برای حل مساله در سایت leetcode.com عضو شوید. برنامه شما زمانی درست است که همه تست ها را پاس کند. از دیدگاه الگونوردی، برنامه شما زمانی کامل است که سرعت آن حداقل از ۹۰ درصد راه حل ها سریع تر باشد. سایت leetcode.com سرعت نسبی برنامه شما را نشان خواهد داد.

زمان بندی: ارسال پاسخ ها تا پایان روز 18 می

نکات مهم:

• انتخاب برنده هر هفته بر اساس اولین پاسخ کامل هست که شرح حل مساله را فراهم آورد. بنابر این اگر به پاسخ کامل رسیده اید معطل نکنید و شرح حل خود را زیر پست بنویسید. تنها زبان برنامه نویسی مورد قبول پایتون می باشد.
• طبق روال برنده مسابقه هر هفته پس از انتخاب باید شرح کامل حل مساله را بنویسد. در انتها من شرح مساله نوشته شده را ویرایش و ارسال خواهم کرد.
• لطفا خودتان مسایل را حل کنید و پاسخ را ارسال نمایید. استفاده از پاسخ های دیگر و ارسال آن جهت الگونوردی با اهداف این حرکت مغایرت دارد. لطفا در این زمینه همکاری نمایید. با ارسال پاسخ زیر این پست تایید می کنید که کد متعلق به خودتان هست و آنرا شخصا حل کرده اید.
• بحث های علمی زیر این پست کاملا آزاد است. اگر در مورد نحوه مدیریت این حرکت پیشنهادی دارید به ایمیل من s.h.siadaty@gmail.com ارسال نمایید.

قوانین اهدای جایزه:

• مبلغ جایزه نقدی 50,000 تومان می باشد.
• تنها یک نفر برنده برای هر هفته اعلام خواهد شد که طبق اولین پاسخ درست و شرح خلاصه می باشد.
• جهت ایجاد مشارکت، در هر فرد تنها می تواند یکبار برنده جایزه در طول یک ماه باشد.
• جایزه نقدی تنها در صورت نوشتن شرح کامل مساله تقدیم خواهد شد.

حل مساله

برنده هفته ۷ الگونورد کاربر با ای دی Iman می باشند.

به Iman تبریک می گم!

و حالا شرح پاسخ:

هدف در این مسئله پیدا کردن عددهای در یک لیست  هست که بیشتر از n/3 (یک سوم طول لیست) تکرار را دارند، در اینجا n برابر تعداد عناصر آرایه است.

حل مسئله را با یک مثال ساده شروع می‌کنیم تا مطمئن شویم که مسئله را به خوبی درک کرده‌ایم، اگر ورودی زیر را داشته باشیم:

[3,3,3,2,1,1]

در این صورت تعداد عناصر آرایه برابر n=6 در نتیجه n/3=2 و پاسخ خروجی برابر با [3,1] خواهد بود، زیرا تعداد تکرار عدد 3 و 1 برابر 3 و تکرار عدد 2 برابر 1 است.

ساده ترین روش حل این مساله آن است که تعداد تکرار هر مقدار را بشماریم و در انتها برای هر مقدار بررسی کنیم که آیا تعداد تکرار از یک سوم طول آرایه بیشتر است. برای شمارش تعداد تکرار هر عنصر می‌توان از یک دیکشنری استفاده نمود که عناصر لیست کلیدهای آن را تشکیل می دهند و مقدار متناظر هر کلید تعداد تکرار آن  در لیست نگهداری می‌کند.

برای این کار می توان یک دیکشنری ساخت و با استفاده از یک حلقه تکرار تعداد تکرارهای عناصر را شمرد. روش متناظر استفاده از ساختار Counter پایتون می باشد که با دریافت یک لیست یک دیکشنری می سازد و تعداد تکرار عناصر را در آن قرار می دهد. پس از انجام شمارش با استفاده از یک حلقه بررسی می کنیم که اگر تعداد تکرار یک عدد بیشتر از n/3 باشد سپس آن را به یک لیست خروجی اضافه می کنیم. قطعه برنامه زیر پیاده سازی این روش را نشان می دهد.

وضیح کد:

در خط 3 با استفاده از متد items دیکشنری را به یک لیست که هر عنصر آن یک تاپل هست تبدیل کردیم و با یک حلقه عناصر تاپل این آرایه را بررسی کرده‌ایم.

پیچیدگی زمانی و حافظه‌ای:

پیچیدگی زمانی این الگوریتم برابر (O(n و پیچیدگی حافظه آن به دلیل استفاده کردن از دیکشنری برابر (O(n می‌باشد. این الگوریتم محدودیت صورت مساله مبنی بر استفاده از تنها (O(1 حافظه را برآورده نمیکند. بنابراین باید حل مساله را بهبود ببخشیم.

نحوه بهبود:

اگر بیشتر روی مسئله تامل کنیم در می یابیم حداکثر 2 عنصر لیست محدودیت مورد نظر یعنی تکرار بیش از یک سوم بار در لیست را برآورده می کنند. دلیل آن این است که اگر سه عنصر بیش از یک سوم بار تکرار می شدند آنگاه شمارش تعداد آنها از طول لیست بیشتر می شد که یک تناقض است.

می توانیم از این خاصیت استفاده نماییم و از استفاده از دیکشنری پرهیز کنیم. یک الگوریتم  مشهور که کمک می کند این کار را انجام دهیم الگوریتم معروف رای اکثریت (majority vote algorithm) بویر- مور  (Boyer–Moore)

است که  عنصری که بیش از نصف طول یک لیست تکرار می شود را می یابد. پیچیدگی زمانی این الگوریتم (O(n و پیچیدگی فضایی آن (O(1  می باشد.

این الگوریتم به این نحو عمل می‌کند که عناصر لیست را می خواند و تنها از یک متغیر m برای نگهداری یک عنصر کاندید و یک شمارنده i برای شمارش تعداد رای به عنصر کاندید استفاده می‌کند. مقدار اولیه این دو متغیر در ابتدا صفر است. سپس در یک حلقه تکرار عناصر لیست را می‌خوانیم. چنانچه شمارنده برابر صفر باشد مقدار عنصر کاندید m را را برابر عنصر کنونی، تنظیم می کنیم مقدار شمارنده را یک می کنیم. در غیر این صورت (شمارنده بزرگتر از صفر)  چنانچه عنصر کنونی برابر عنصر کاندید باشد یک واحد به شمارنده اضافه می‌کنیم و در غیر اینصورت (چنانچه مقدار برابر عنصر کاندید نباشد) شمارنده را یک واحد کاهش خواهیم داد. شبه الگوریتم این الگوریتم را در زیر مشاهده می‌کنید:

با پایان پیمایش لیست و اجرای الگوریتم، مقداری در متغیر m خواهد بود فارغ از اینکه که آیا لیست یک عنصر اکثریت دارد. اما چنانچه عنصر اکثریت داشته باشد، مقار آن m می باشد. برای اطمینان، باید یکبار دیگر لیست را پیمایش کنیم و تعداد تکرار m را بشماریم و نهایتا با طول لیست مقایسه نماییم.  

تصویر زیر حالت الگوریتم رای حداکثریت بویر-مور را برای یک مثال از لیست مقادیر (که با اشکال دایره، مربع و ستاره مشخص شده اند) نشان می دهد، ورودی‌ها در امتداد محور افقی نشان داده شده اند و   محور عمودی مقدار متغیر شمارنده i را نشان می دهد:

الگوریتم بویر-مور را می توان برای حل مساله یافتن عناصر بیش از یک سوم استفاده نمود. به جای استفاده از یک عنصر کاندید دو عنصر کاندید (t) در نظر می گیریم. همچنین دو عنصر شمارنده (c) در نظر می گیریم.  

با این اوصاف شروع به نوشتن برنامه زیر می کنیم. در خط 2 متغیرهای مورد نیاز را تعریف می کنیم. در خط 3 تا 14 الگوریتم بویر مور را جهت به دست آوردن دو عددی که بیشترین تکرار را دارند، تعریف پیاده کرده ایم با این تفاوت که شرط های شمارش را برای دو عنصر کاندید تغییر داده ایم. در خط 16 تا 21 تعداد تکرار این دو عدد را در رشته محاسبه کرده‌ایم. در خط 23 تا 26 شروطی گذاشته‌ایم که اگر تعداد تکرار این دو متغیر توالی بیشتر n/3 بود آن را به بردار خروجی نهایی اضافه کند.

پیچیدگی زمانی و حافظه‌ای:

پیچیدگی زمانی این الگوریتم برابر(O(n و پیچیدگی حافظه آن برابر(O(1 می‌باشد.