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))