اولین بار است که به این وب‌سایت می‌آیید. راهنما را مطالعه کنید!
x
موسسه خیریه محک

شهر ریاضی بازی-ریاضی

برای پیدا کردن مد یا خانه ای که بیشتر از همه تکرار شده در یه آرایه ی تک بعدی چیکار باید کرد؟

+1 امتیاز
3,257 نمایش
پرسیده شده پنجشنبه ۹ خرداد ۱۳۹۲ در C++ توسط سالار  

1 پاسخ

0 امتیاز
 
بهترین پاسخ

در صورتی که بازه‌ی اعداد مورد استفاده کوچیک باشه مثلاً ۱ تا ۱۰۰ باشه. در این صورت می‌شه یه آرایه‌ی ۱۰۰ تایی ساخت که تعداد هر کدوم از اعداد رو نگه می‌داره

int count[100] = {0}:
for(int i=0; i<n; i++)
    count[array[i]]++;

در صورتی که اسم آرایه‌ی اولیه array باشه که n خونه داره.

اما در حالت کلی این روش حافظه‌ی زیادی مصرف می‌کنه. چون ممکنه array آرایه‌ای از اعداد long int باشه که نمی‌شه برای هر عددش یه خونه‌ی آرایه در نظر گرفت. در این صورت من دو یه راه به نظرم می‌رسه.
ابتدا آرایه رو مرتب می‌کنیم. حالا فرض کنیم آرایه‌ی مرتب شده array با n عضو باشه. الگوریتم زیر مد رو می‌ده

int number = 0, count = 0, max_number = 0, max_count = 0;
number = max_number = array[0];
count = max_count = 1;

for(int i=1; i<n; i++)
{
    if(number == array[i])
    {
        count++;
    }
    else
    {
        if(count > max_count)
        {
            max_count = count;
            max_number = number;
        }
        count = 1;
        number = array[i];
    }
}
هیچ پژوهش انسانی نمی‌تواند ادعای علمی بودن داشته باشد، مگر این‌که از برهان ریاضی برخوردار باشد (لئوناردو داوینچی)
پاسخ داده شده پنجشنبه ۹ خرداد ۱۳۹۲ توسط prodo  
انتخاب شده پنجشنبه ۹ خرداد ۱۳۹۲ توسط سالار