پیدا کردن بیشترین آیتم تکرار شده در یک لیست

[sara_aryanfar]

با سلام فرض کنید ما لیستی داریم که آیتم های اون اعداد هستند و هرکدوم اینها چندین بار تکرار شدند ما چطور می تونیم عددی رو پیدا کنیم که بیشترین دفعات تکرار رو داشته؟

[veniz2008]

سلام.
کد زیر عدد (یا اعدادی) رو که بیشترین تکرار رو دارن به همراه تعداد تکرار اون عدد (یا اعداد) رو نشون میده .

int count = maxcount =0;
string result = "";
for(int i = 0;i<listBox1.Items.Count;i++)
for (int j = 0; j < listBox1.Items.Count; j++)
{
if (listBox1.Items[i] == listBox1.Items[j])
count++;
if (j == listBox1.Items.Count - 1)
{
if (count > maxcount)
{
maxcount = count;
result = listBox1.Items[i].ToString();

}
else if (count == maxcount)
{
if(!result.Contains(listBox1.Items[i].ToString()))
result += "," + listBox1.Items[i].ToString();
}
count = 0;
}
}
MessageBox.Show("بیشترین تکرار مربوط به اعداد : " + result + " با میزان تکرار " + maxcount.ToString() + " می باشد ");
موفق باشید.

[Mahmoud.Afrad]

میتونید لیست اعداد رو گروهبندی کنید و گروهها رو برحسب تعداد اعضا به صورت نزولی مرتب کنید و گروه اول (که قطعا دارای بیشترین اعضا هست) را انتخاب کنید و مقدار اون گروه رو بخونید.
مثال:

List<int> lst = new List<int>() { 5, 6, 2, 5, 4, 1, 8, 7, 7, 5, 4, 2, 4, 9, 7, 5 };
var k = (from i in lst
group i by i into g
orderby g.Count() descending
select g)
.First()
.Key;
//int k = lst.GroupBy(i => i).OrderByDescending(i => i.Count()).First().Key;
MessageBox.Show(k.ToString());

[veniz2008]

میتونید لیست اعداد رو گروهبندی کنید و گروهها رو برحسب تعداد اعضا به صورت نزولی مرتب کنید و گروه اول (که قطعا دارای بیشترین اعضا هست) را انتخاب کنید و مقدار اون گروه رو بخونید.
مثال:

List<int> lst = new List<int>() { 5, 6, 2, 5, 4, 1, 8, 7, 7, 5, 4, 2, 4, 9, 7, 5 };
var k = (from i in lst
group i by i into g
orderby g.Count() descending
select g)
.First()
.Key;
//int k = lst.GroupBy(i => i).OrderByDescending(i => i.Count()).First().Key;
MessageBox.Show(k.ToString());

این کد اگر یک گروه بیشترین تکرار رو داشته باشه بدرستی کار میکنه ولی اگر دو یا چند گروه تعداد تکرار یکسان داشته باشند، جواب صحیح رو برنمیگردونه. مثلا فرض کنید به جای عدد 6، عدد 7 رو بذاریم و تعداد تکرار 7 مثل تعداد تکرار 5 به 4 تا برسه، باز هم عدد 5 رو نشون میده که خروجی صحیحی نیست.

[Mahmoud.Afrad]

این کد اگر یک گروه بیشترین تکرار رو داشته باشه بدرستی کار میکنه ولی اگر دو یا چند گروه تعداد تکرار یکسان داشته باشند، جواب صحیح رو برنمیگردونه. مثلا فرض کنید به جای عدد 6، عدد 7 رو بذاریم و تعداد تکرار 7 مثل تعداد تکرار 5 به 4 تا برسه، باز هم عدد 5 رو نشون میده که خروجی صحیحی نیست.
در صورتی که گروه ها بر حسب تعداد اعضاء به صورت نزولی مرتب بشن پس اولین گروه قطعا دارای بیشترین تعداد هست. برای پیدا کردن گروه های هم تعداد ، در اینصورت گروه هایی که با گروه اول تعداد یکسانی دارند رو انتخاب میکنیم:

List<int> lst = new List<int>() { 1, 2, 2, 3, 3 };
var allGroups = from i in lst
group i by i into g
orderby g.Count() descending
select g;
//var allGroups = lst.GroupBy(i => i).OrderByDescending(g => g.Count());

var groupsWithMaxCount = from j in allGroups
where j.Count() == allGroups.First().Count()
select j;
//var groupsWithMaxCount = allGroups.Where(j => j.Count() == allGroups.First().Count());
foreach (var g in groupsWithMaxCount)
{
listBox1.Items.Add(g.Key);
}

[samad1987]

به نظر من از لحاظ زمانی این روش سریعترینه:
اول sort کن داده هاتو
بعد خیلی راحت :


max=1;
counter=1;
item=a[0]
for (i=1;i<n;i++)
if(a[i]==a[i-1])
counter++;
else {
if(max<counter)
{
max=counter;
item=a[i-1];
}

counter=1;

}



پیچیدگی زمانی در بدترین شرایط nlogn هستش و میتونم بگم کمتر از این نمیشه و اونم به خاطر مرتب سازیشه

[Mahmoud.Afrad]

جز این هست که نیاز به دو حلقه for تو درتو داری؟. یعنی n^2 . درسته که میشه حلقه رو طوری بهینه کرد که از پیمایش بیهوده و اضافی جلوگیری کرد (نیازی به مقایسه هر عدد با تمام اعداد نخواهد بود. به محض اینکه هر عدد با عدد بعدی برابر نبود، مقایسه رو ادامه نمیدیم) ولی باز هم مرتبه اجرای برنامه n^2 خواهد بود.

چون لیست مرتب شده نیازی به دو حلقه تودرتو نیست، کافیه با یک حلقه تعداد اعداد یکسان محاسبه و این تعداد رو مقایسه کرد.
فرض کنیم لیست به صورت نزولی مرتب شده. خب عدد اول رو به عنوان معیار انتخاب میکنیم و در هر بار اجرای حلقه اونو با عنصری که شمارنده حلقه بهش اشاره میکنه مقایسه کنیم، اگر برابر بود یکی به counter اضافه میشه، اگر نبود معیار رو تغییر میدیم به عنصر جاری و تعداد بدست اومده رو در یک متغیر دیگه ذخیره میکنیم. و counter رو 1 میکنیم.
برای معیار جدید تعداد رو مقایسه میکنیم. اگر تعداد این عدد با تعداد عدد اول برابر بود اون عدد قابل قبوله. مرتبه زمانی این حلقه برابر n خواهد بود.
اگر مرتبه زمانی الگوریتم مرتب سازی nlogn باشه مرتبه زمانی کل محاسبات در بدترین شرایط nlogn + n = nlogn خواهد بود.


lst = new List<int>() { 3, 3, 2, 1, 1 };
int maxCounter = 1, counter = 1, pointer = 0;
for (int i = 1; i < lst.Count; i++)
{
if (lst[i] == lst[pointer])
{
counter++;
}
else
{
if (pointer == 0)
{
maxCounter = counter;
}

if (counter == maxCounter)
{
listBox1.Items.Add(lst[pointer]);
}

pointer = i;
counter = 1;
}
}
if (counter == maxCounter)
{
listBox1.Items.Add(lst[pointer]);
}

[samad1987]

عزیز دلم .. فدات شم .. اون کدی که من نوشتم یه حلقه بیشتر نداره . مکانیزم کار اینطوریه که شمارنده میشمره تا اینکه داده امN با N-1 ام متفاوت باشه که در اینصورت شمارنده صفر میشه البته قبل صفر شدن چک میکنه که آیا max هست یا نه ؟؟
الان به نظرت پیمایش یک لیست ساده بیشتر از n وقت میبره ؟؟؟؟؟
n+nlogn=nlogn
آیا حرفمو تایید میکنی؟

[tooraj_azizi_1035]

var most = list.GroupBy(i=>i).OrderByDescending(grp=>grp.Count()) .Select(grp=>grp.Key).First();

[alireza_kaka]

يك سوال:
اگه بخوايم 3 تا آيتمي رو كه به ترتيب بيشترين تكرار رو دارن پيدا كنيم چيكار بايد كرد؟