Strona główna » Algorytmy » Artykuły » Zliczanie wystąpień elementu
 

Zliczanie wystąpień elementu

https://mattomatti.com/a0014

Przypadek ogólny zliczania elementów

W celu zliczenia ilości wystąpień wybranego elementu na dowolnej liście wystarczy algorytm o złożoności liniowej Θ(n). Wykorzystuje on jedną zmienną do zliczania i pętle, aby sprawdzić każdy element na liście. Kod realizujący to zadanie wygląda następująco:

  1. int ileWystapien(int* dane, int dl, int a) {
  2.   int licznik = 0;
  3.   for (int i = 0; i < dl; i++) {
  4.     if (dane[i] == a) {
  5.       licznik++;
  6.     }
  7.   }
  8.   return licznik;
  9. }

Zliczanie na liście posortowanej

Poprzedni kod zadziała dla dowolnej listy. Warto jednak zastanowić się na przypadkiem, gdy zliczane są elementy na liście posortowanej. Wtedy wszystkie wystąpienia szukanego elementu znajdują się na liście koło siebie.

W takim przypadku znając pierwszą pozycję szukanego elementu oraz ostatnią można policzyć ile takich elementów występuje na liście. Wykorzystanie do tego celu wyszukiwania binarnego można zmniejszyć złożoność algorytmu do Θ(logn).

Wyszukiwanie pierwszego elementu

Pierwszego wystąpienia na liście szukanego elementu a zajmuje się funkcja szukajPierwszy(), która szuka na liście dane o długości dl wartości a na indeksach z zakresu [zakrL, zakrP] w sposób rekurencyjny. Jest to kod oparty na wyszukiwaniu binarnym. W przypadku znalezienia elementu zwracany jest jego indeks, a w przypadku, gdy dany element nie istnieje to zwracana jest wartość -1.

  1. int szukajPierwszy(int* dane, int dl, int zakrL, int zakrP, int a) {
  2.   if (zakrP >= zakrL) {
  3.     int zakrM = (zakrL + zakrP) / 2;
  4.     if ((zakrM == 0 || a > dane[zakrM - 1]) && dane[zakrM] == a) {
  5.       return zakrM;
  6.     } else if (a > dane[zakrM]) {
  7.       return szukajPierwszy(dane, dl, zakrM + 1, zakrP, a);
  8.     } else {
  9.       return szukajPierwszy(dane, dl, zakrL, zakrM - 1, a);
  10.     }
  11.   }
  12.   return -1;
  13. }

(2.) Dopóki zakres nie jest pusty to: (3.) wyznacz indeks środkowego elementu. (4.) Jeśli został znaleziony szukany element i jest to większy element od poprzedniego na liście lub jest to pierwszy element to (5.) należy zwrócić indeks. W przeciwnym razie (6.) należy określić po której stronie jest szukany element od pozycji środkowej. (7.) Jeśli element a jest większy od elementu na środkowej pozycji to (8.) należy szukać na prawo od indeksu środkowego, a w przeciwnym wypadku (10.) na lewo od środkowego elementu. (13.) W przypadku, gdy przeszukiwany zakres zostanie wyczerpany, a szukana wartość nie zostanie odnaleziona to należy zwrócić -1.

W powyższym kodzie krytyczna jest linijka (4.). Tam w przeciwieństwie do typowego wyszukiwania binarnego program musi upewnić się, że znalazł pierwszy taki element na liście.

Wyszukiwanie ostatniego elementu

Analogicznie do wyszukiwania pierwszego elementu a na liście działa funkcja szukajOstatni(), która znajduje ostatni element a na liście. Tak samo jak w poprzednim przypadku jeśli element nie zostanie odnaleziony to funkcja zwraca -1.

  1. int szukajOstatni(int* dane, int dl, int zakrL, int zakrP, int a) {
  2.   if (zakrP >= zakrL) {
  3.     int zakrM = (zakrL + zakrP) / 2;
  4.     if ((zakrM == dl - 1 || a < dane[zakrM + 1]) && dane[zakrM] == a) {
  5.       return zakrM;
  6.     } else if (a < dane[zakrM]) {
  7.       return szukajOstatni(dane, dl, zakrL, zakrM - 1, a);
  8.     } else {
  9.       return szukajOstatni(dane, dl, zakrM + 1, zakrP, a);
  10.     }
  11.   }
  12.   return -1;
  13. }

Liczenie wystąpień

Tak samo jak w przypadku o złożoności liniowej funkcja ileWystapien() przyjmuje trzy argumenty: dane - lista na której ma zostać element a, dl - długość listy dane, a - element do wyszukiwania.

  1. int ileWystapien(int* dane, int dl, int a) {
  2.   int wystL = 0, wystP = 0;
  3.   wystL = szukajPierwszy(dane, dl, 0, dl - 1, a);
  4.   if (wystL == -1)
  5.     return 0;
  6.   wystP = szukajOstatni(dane, dl, i, dl - 1, a);
  7.   return wystP - wystL + 1;
  8. }

(2.) Zainicjalizuj zmienne do zapisu indeksu pierwszego i ostatniego elementu. (3.) Wyszukaj pierwszy element na liście i (4.) jeśli nie zostanie znaleziony to (5.) zwróć, że jest 0 elementów a na liście. W przeciwnym razie (6.) znajdź ostatni element na liście dane i (7.) zwróć ile elementów a zostało znalezionych.

Testowanie funkcji

W celu przetestowania działania funkcji można skorzystać z poniższej funkcji main():

  1. int main() {
  2.   int dl = 10;
  3.   int dane[] = { 1, 2, 2, 3, 3, 3, 4, 4, 4, 4 };
  4.   cout << ileWystapien(dane, dl, 3) << endl;
  5.   system("pause");
  6.   return 0;
  7. }