دفعات تکرار هر عنصر درون آرایه

[shayan100]

با سلام
اگه بخوام تعداد دفعات تکرار تمامی عنصر های یک آرایه رو بدست بیارم دقیقا باید چی کار کنم ؟
بر فرض مثال :
یه آرایه ای دارم که عناصرش : 1.2.1.1.3.5.8.8.3.
هست بعد طبق چه الگوریتمی تعداد دفعات تکرار تمامی عناصر رو بدست بیاریم
در واقع بهمون بگه 1 سه بار تکرار شده
8 دوبار
2 یکبار
3دوبار و بهم ترتیب
ممنون میشم راهنمایی بفرمایید ؟

[sa1378]

با سلام
اگه بخوام تعداد دفعات تکرار تمامی عنصر های یک آرایه رو بدست بیارم دقیقا باید چی کار کنم ؟
بر فرض مثال :
یه آرایه ای دارم که عناصرش : 1.2.1.1.3.5.8.8.3.
هست بعد طبق چه الگوریتمی تعداد دفعات تکرار تمامی عناصر رو بدست بیاریم
در واقع بهمون بگه 1 سه بار تکرار شده
8 دوبار
2 یکبار
3دوبار و بهم ترتیب
ممنون میشم راهنمایی بفرمایید ؟
فرض کن این رسته رو توی[ a[ n بریزی
حالا دوتا رشته دیگه[ b[ n و[ c[ n هم میسازیم که مقدار اولیشون صفره
اول یه مقدار p میزاریم که برابر 0 هست
یه حلقه میزاریم تا به ازای تمام اعضای a این کارو انجام بده:
تمام اعضای b رو بگرد و اگه[ a[ i برابر با[ b[ j بود[ c[ j رو یکی زیاد کن
اگه برابر هیچکدوم نبود :
[ b[ p ر برابر با [ a[ i قرار بده و [ c[ p و p رو هم یکی زیاد کن

کد:(به ازای ورودی صفر جواب نمیده)
#include <iostream>
using namespace std;
#define N 1000
int n,a[N],b[N],c[N],p,ex;

int main() {

cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];

for(int i=0;i<n;i++)
{
ex=0;
for(int j=0;j<n;j++)
{
if(a[i]==b[j])
{
ex++;
c[j]++;
break;
}
}
if(ex==0)
{
b[p]=a[i];
c[p]++;
p++;
}

}

for(int i=0;b[i]!=0;i++)
cout<<b[i]<<" "<<c[i]<<"\n";



return 0;
}

[rahnema1]

اگه دامنه اعداد مشخص باشه یعنی معلوم باشه اعداد ورودی بین 0 تا 9 هستند پس یک آرایه 10 عضوی برای ثبت تعداد ایجاد کنید به نام hist

int arr[9] = {1,2,1,1,3,5,8,8,3};
unsigned int hist[10] = {};
for (int i=0; i < 9; i++)
hist[arr[i]]++;
for (int i=0; i < 10; i++)
cout << i << ":" << hist[i] << "\n";

[a.r.khoshghalb]

سلام
راه sa1378 (http://barnamenevis.org/member.php?328614-sa1378) هم خوبه ولی خوب اوردرش زیاده! (n^2)
2 تا راه با اوردر nlogn هست (من 2 تا به ذهنم میرسه الان) یکی اینکه هر عددی که ورودی گرفتی رو توی multiple set بریزی و بعد تهش از اول تا آخر ست برای هر عدد upper bound منهای lower bound اش رو چاپ کنی.
راه دوم اینه که از map استفاده کنی! هر عدد که ورودی گرفتی یه خونه براش توی مپ میسازی و یکی زیاد میکنی مقدارش رو!
اگر اعدادت کوچک باشند و خیلی بزرگ نشن میتونی حتی از آرایه استفاده کنی!
هر کدوم از راه حل ها رو توضیح بیشتر خواستی بگو. کد هم اگر خواستی بگو.
حالا برای مسابقه تبیان که دنبال جواب این سوال نبودی؟ بودی؟ اگه بودی باید بگم اون سوال رو لازم نیست اینجوری حل کنی! اگر هم نبودی که هیچی.

[shayan100]

نه برا مسابقه نبود برای حل یه مسئله بهش نیاز داشتم
البته دو تا راهی که دوستان گفتن خیلی کمکم کرد
راهه اول که فرمودید دقیقا به چه شکلی هست ؟ ممنون میشم توضیح بدید
بعد اگه اندیس محل های تکرار رو هم بخواهیم به چه شکل هست یعنی در واقع مقدار 1 مثلا در محل های 0.5.7 تکرار شده ؟
با تشکر

[a.r.khoshghalb]

اعداد آرایه ات حداکثر چند هستند؟

[shayan100]

اعداد آرایه ات حداکثر چند هستند؟

بر فرض 10 تا

[a.r.khoshghalb]

منظورم رو اشتباه فهمیدی، نپرسیدم آرایه ات حداکثر چند تا عدد داره. منظورم این بود که هر عدد حداکثر چنده! اگر حداکثر 6^10 باشه یه راه خوبش اینه که یه آرایه از وکتور ها بگیری به اندازه حداکثر مقدار هر عدد (که فرض کردیم 6^10 باشه). بعد هر عددی که خوندی، به وکتورش، اندیسش رو اضافه کنی.
کد:

#include <iostream>
#include <vector>

using namespace std;

vector<int> tedad[1000001]; // tedad tekrare har adad va andis ro into negah midarim

int main()
{
int n; // tedad adad ha
cin >> n;
int x[100001]; // arraye adad ha
for (int i = 0; i < n; i++)
{
cin >> x[i];
tedad[x[i]].push_back(i);
}
}


الان توی این کد تعداد تکرار عددی مثل q برابر است با ()tedad[q].size
و اندیس هایی که عددی مثل q اومدن، توی وکتور [tedad[q هست.

[shayan100]

منظورم رو اشتباه فهمیدی، نپرسیدم آرایه ات حداکثر چند تا عدد داره. منظورم این بود که هر عدد حداکثر چنده! اگر حداکثر 6^10 باشه یه راه خوبش اینه که یه آرایه از وکتور ها بگیری به اندازه حداکثر مقدار هر عدد (که فرض کردیم 6^10 باشه). بعد هر عددی که خوندی، به وکتورش، اندیسش رو اضافه کنی.
کد:

#include <iostream>
#include <vector>

using namespace std;

vector<int> tedad[1000001]; // tedad tekrare har adad va andis ro into negah midarim

int main()
{
int n; // tedad adad ha
cin >> n;
int x[100001]; // arraye adad ha
for (int i = 0; i < n; i++)
{
cin >> x[i];
tedad[x[i]].push_back(i);
}
}


الان توی این کد تعداد تکرار عددی مثل q برابر است با ()tedad[q].size
و اندیس هایی که عددی مثل q اومدن، توی وکتور [tedad[q هست.


بله من درست منظورتونو نفهمیدم ... !
ممنونم ولی راهی نیست که از وکتور استفاده نکنیم خودم یه راههی به ذهنم زد منتها خیلی طولانیه و کاربردی نداره در واقع وقتی ما یه آرایه داریم که تعدادش مشخصه
بگیم
if (arr[i] == 0)
cout <<"about 0 : "<< i;

مثلا 0 در اندیس ها میباشد که خیلی طولانی میشه و برای آرایه های که تعدادش مشخصه به کارمون میاد :|

[sajad1414]

سلام و تشکر از برنامه. من برنامه رو نوشتم و اجرا شد مشکلی که دارم اینه که در آرایه b , c که تعریف کردیم روند محاسبه رو متوجه نمی شم اینکه خانه ها برای آرایه b چطور در نظر گرفته میشه , و اعداد چطور قرار میگیرن و اندیس برای این دو چطور در نظر گرفته میشه.خیلی ممنون میشم بفرمایید این قسمت رو
{ ex++;
c[j]++;
break;
}
}
if(ex==0)
{
b[p]=a[i];
c[p]++;
p++;
}

[ServentOfAllah]

دوست عزیز میتونید از هشمپ استفاده کنید به این صورت که هش مثلا عدد باشه و مپش هم عددی که نشون بده چند بار اون عدد تکرار شده. اینجوری فقط لازمه آرایه رو یکبار بخونید یعنی o(n) هست.