Janusz Skop, 4508

2zBinf

Zadanie:
Podaj algorytm, który znajduje w tablicy a[0],...,a[n-1] najczęściej występujący element.
Postaraj się, aby czas działania Twojego rozwiązania był jak najmniejszy. Algorytm
w pełni rozwiązujący to zadanie powinien działać w czasie O(n

⋅

k), gdzie k to liczba

różnych elementów występujących w tablicy.
Przykład
W tablicy a=[5, 7, 13, 7, 5, 5, 7] wartość k wynosi 3, ponieważ występują w niej trzy
różne elementy: 5, 7, 13.

Rozwiązanie:

Specyfikacja:

Dane: tablica n-elementowa a
Wynik: najczęściej występująca wartość w tablicy a[]

Implementacja:

int Przeszukaj(int a[], int n)
{

int *b=new int [n];
for (int i=0; i<n; i++) b[i]=a[i];

int licznik,w, wmax=b[0], wlmax=0;
for (int i=0; i<n; i++)

{
w=b[i];

licznik=1;
for (int j=i+1; j<n; j++)

if (w==b[j])
{

b[j]=b[i+licznik];
b[i+licznik]=w;

licznik++;
}

if (licznik>wlmax)
{

wlmax=licznik;
wmax=w;

}
i+=licznik;

}
delete []b;

return wmax;
}

~O(n*(n-wlmax))