آرایه غیر مرتب بهترین الگوریتم برای نمایش تعداد تکرار

[sohrab o]

سلام دوستان
در یک آرایه غیر مرتب، بهترین الگوریتم برای نمایش تعداد تکرار عناصر چگونه است؟
مثلا : آرایه=5 6 4 2 6 4 8 3 5 1 5
5 3 بار
1 1 بار
6 2 بار
8 1 بار
4 2 بار
2 1 بار
3 1 بار

تورو خدا جواب بدین خیلی گیرم

[hossein taghi zadeh]

با سلام

کافی است آرایه‌ اعداد نامرتب را یکبار پیمایش کنید
و آرایه‌ای دیگر داشته باشید که هر خانه‌ی آن تعداد هر عدد را نگهداری می‌کند و اندیس مربوطه همان عدد است، برای مثال:

OutArray: Array[1..1000] Of Integer = {0}; // I = integer OutArray[I] = Count of repeat I

MyArray: Array[1..500] Of Byte; // Input Array Of not sorted integers



For I := 1 to 500 Do

 OutArray[MyArray[I]]++;



For I := 1 To 1000 Do	

  If OutArray[I] > 0 Then

     Writeln(I, ' : ', OutArray[I]);

[sohrab o]

مرسی
اما این الگوریت زمان زیادی استفاده می کنه، باید یه الگوریتم دیگه باشه که زمان بهتری داشته باشه
این وسالو واسه درس طراحس الگوریتم می خوام

[whitehat]

زمانی که شما باید تمام عناصر آرایه را پیمایش کنید ، درجه پیچیدگی شما N است ، مگر اینکه چند پردازنده داشته باشید و بخواهید موازی کار کنید.

[sohrab o]

مرسی اما من بهترین زمانو میخوام.مثلا یه روش اینه که از یه آرایه کمکی استفاده کنیم
یکی دیگه اینه که جابجایی داشته باشیم

[molla652003]

bayad az segment tree estefade koni

khodam ham khub balad nistam

search kon , oeyda mikoni

[404_3140]

شما باید لا اقل یه بار ورودی رو بخونید. پس مرتبه الگوریتم شما نمی تونه کمتر از n باشه. در مورد مطلبی هم که دوستمون گفتند: کافیه برای چاپ خروجی هم یه دور آرایه رو طی کنید و هر عدد غیر ۰ ی رو که چاپ می کنید شمارنده اش رو ۰ کنید تا تکرار نداشته باشیم. این طوری زمان اجرا از مرتبه n و حافظه به مقدار MAXN لازمه.
سگمت تری هم در این مورد کمکی در کم کردن مرتبه الگوریتم نمی تونه کمکی کنه به همون دلیلی که اول گفتم.

[sohrab o]

متوجه نشدم
می شه با مثال توضیح بدید

[404_3140]

توضیحی بهتر از نوشتن برنامش بلد نیستم:دی

#include<iostream>

using namespace std;

int n;

int a[100],num[100];

int main(){

    cin>>n;

    for(int i=0;i<n;i++){

        cin>>a[i];

        num[a[i]]++;

    }

    for(int i=0;i<n;i++)

        if(num[a[i]]){

            cout<<a[i]<<" "<<num[a[i]]<<endl;

            num[a[i]]=0;

        }

    return 0;

}

[404_3140]

راستی! اینو یادم رفت بگم: اون ۱۰۰ ها که تابلو هست فرمالیته هستن. معمولا سایز num باید بزرگتر از a گرفته شه. دلیلش هم که بدیهیه. فرق این هم با اون کد پاسکالی که بالا هست در اینه که اون با MAXN کار می کنه اما این به اندازه سایز ورودی تایم می بره....