Algorytm do znalezienia najczęściej występującej liczby w tablicy n-elementowej

Question

Witam Poszukuję algorytmu, który zwróci mi z tabeli n-elementowej liczbę, która występuje największą ilość razy. Np. mam tablicę 4-elementową z liczbami [5,0,5,5] i jak widać 5 występuje aż 3 razy i taką wartość ma mi zwrócić. Próbóję ułożyć jak najszybszy algorytm do tego. Póki co doszedłem do...

BoskiDialer · Answer

1/ Sortowanie szybkie + szukanie najdłuższego ciągu. Sortowanie o złożoności O(n log n), szukanie najdłuższego ciągu można zrobić w O(n), co wynika z tego, że ponieważ całość jest posortowana, wystaczą 3 zmienne - aktualnie maksymalna długość wykrytego ciągu, wartość prezentowana przez ciąg i liczba powtórzeń przy skanowaniu (zwiększane jesli kolejny element jest równy, jeśli element różny, to wtedy z założeniami algorytmu przypisuje się liczbę powtórzeń i wartość do wyniku albo nie).
2/ Jeśli wartości są ograniczone do np jednego bajtu, to wydajny będzie uproszczony algorytm sortowania kubełkowego, potem szukasz kubełka o największej wartości i zwracasz jego index (lub można dokonać aktualizacji w locie przy skanowaniu, ale to nie będzie wydajne przy długich tablicach)
Aktualnie więcej pomysłów nie mam.

Sam Sung · Answer

W przypadku ograniczonego zakresu liczb w tablicy, można zliczyć liczbę wystąpień każdej możliwej wartości (pierwszy etap sortowania pozycyjnego) - czas O(n), gdzie n to długość tablicy - i następnie znaleźć w utworzonej tablicy indeks maksimum - czas O(m), gdzie m to szerokość zakresu.

autoservice · Answer

... w tym sęk, że każda wartość to zakres 0...255 więc za dużo. Ilość elementów w tablicy to 4. Narazie doszedłem do takiego właśnie rozwiązania ale nie sprawdzam każdą z możliwych wartości , lecz tylko te wartości, które mam w tablicy. Czyli biorę pierwszą pozycję z tablicy i sprawdzam ile razy ona występuje, potem drugą pozycję i też sprawdzam ile razy występuje aż do 4 pozycji. Ta która wystąpi najwięcej razy jest poprawna...
Pzdr.[/url]

Sam Sung · Answer

Twój algorytm ma kwadratową złożoność czasową, ale jest prosty, więc jeśli tablica ma zawsze tylko 4 elementy, to chyba nie uda się tego przyspieszyć stosując bardziej wyrafinowane algotytmy. Jedyne proste usprawnienie, jakie mi się nasuwa, to nie przeszukiwanie całej tablicy 4 razy, a tylko podtablicę od n-tego elementu do ostatniego.
Rozumiem, że program ma być napisany na jakiś mikrokontroler, skoro nie ma miejsca na tymczasową 256-bajtową tablicę?

Promuję tematy:
31.01.2026 Termometr z czujnikiem DS18B20 i dwucyfrowym wyświetlaczem LED
19.01.2026 Prostownik do doładowywania akumulatora w aucie
07.07.2025 Watomierz optyczny za 10 zł
29.09.2022 USB power booster na LM2596S

autoservice · Answer

...dla moich celów mogę go jeszcze uprościć, tzn przy pierwszym sprawdzaniu tj założeniu, że 1 element tablicy jest poprawy i gdy on wystąpi 3x to mogę dalej nie sprawdzać. Do czego mi ten algorytm?...zapisuję jedną daną typu char w eeprom'ie, w jednej komórce. Przypadkiem ta komórka zmieniła wartość (zakłócenia itp) no i lipa urządzenie może stanąć w miejscu.
Ale gdy zapiszę tą daną w 4 miejsach odległych od siebie o 100 komórek to prawdopodobieństwo, że zostaną zmienione właśnie 4 na raz jest znikome... wystarczy mi nawet, że dwie wartości z tych komórek będą poprawne.
Mam zamiar dodać też funkcję automatycznego odświeżania jeśli któraś z tych 4 komórek zmieni wartość, własnie na podstawie ilości wystąpień danej z komórek.
Pzdr.

BoskiDialer · Answer

Jeśli całość to zawsze 4 komórki, to można dokonać troche optymalizacji:
- przypadek, kiedy wszystkie 4 komórki mają różną wartość, wtedy algorytm zakończy się niepowodzeniem
- przypadek, kiedy istnieją 2 komórki o tych samych wartościach. Gdy pozostałe dwie komórki będą między sobą równe, ale o różnej wartości niż pozostałe dwie, algorytm nie będzie mógł dokonać rozróżnienia
- przypadek, kiedy istnieją 2 komórki o tych samych wartościach, ale pozostałe dwie mają wartości różne między sobą oraz między parą - tutaj istnieje jednoznaczne rozwiązanie
- przypadek, kiedy istnieją 3 komórki o tych samych wartościach - też jedno rozwiązanie
- przypadek, kiedy są 4 komórki identyczne
w uproszczeniu wystarczy znaleźć 2 komórki o tej samej wartości i zwrócić ich wartość: przypadek z 4 i 3 równymi będzie rozpoznany bezbłędnie, przypadki z 2 równymi będą rozpoznane: gdy pozostała para liczb różna - dokładne - gdy pozostała para liczb równa - z błędem, którego nie da się skorygować
Uproszczenie chyba wystarczające. W kodzie wyglądało by to jakoś tak:

char repcell(char a, char b, char c, char d)
{
  if(a==b || a==c || a==d)
    return a;
  if(b==c || b==d)
    return b;
  if(c==d)
    return c;
  // brak dwóch liczb o tej samej wartości..
  return d; // return 0;
}

autoservice · Answer

...jednak rozwiązałem troszku inaczej, bardziej uniwersalnie... a mianowicie zliczam ile razy w tablicy wystepuje kazda wartosc z tablicy. Rozwiazanie uniwersalne dla dowolnej dlugosci tablicy i najskuteczniejsze...prawie zawsze jednoznacznie okresla, ktora dana wystepuje najwieksza ilosc razy. przy tablicy 10 elementow jest bardzo malo prawdopodobne aby przypadkiem 5 komorek zapisalo sie innymi takimi samymi wartosciami...
Problem rozwiązany.

Pzdr.

Algorytm do znalezienia najczęściej występującej liczby w tablicy n-elementowej

Post #1

Post #2

Post #3

Post #4

Post #5

Post #6

Post #7

Post #8

Podsumowanie tematu