Strona główna » Algorytmy » Artykuły » Unikalne Elementy Tablicy
 

Unikalne Elementy Tablicy

https://mattomatti.com/a0205

Cel

Dana liczba może zostać zapisany w tablicy wiele razy. Napisz algorytm, który wybierze z podanej, nieposortowanej tablicy liczb wszystkie unikalne elementy. Przykładowo jeśli dana jest lista [3, 2, 1, 3, 3, 2] to ma ona tylko trzy unikalne wartości, którymi są [1, 2, 3].

Opis problemu

W tym przypadku elementami tablicy są liczby, ale mogłyby też być bardziej rozbudowanymi strukturami. Tego typu algorytm może się przydać podczas pracy z bazami danych. Przykładowo wiele osób może mieć to samo imię. Jeśli wybierzemy tylko unikalne imiona z listy wszystkich dowiemy się ile imion jest aktualnie używanych.

Implementacja

Czy już był?

Pierwsza wersja algorytmu polega na wybieraniu każdego kolejnego elementu i dopisywani go do wyniku tylko pod warunkiem, że żaden z poprzednich elementów nie był taki sam. Oznacza to, że dla i-tego elementu należy wykonać i-1 porównań. Złożoność takiego algorytmu jest kwadratowa tj. O(n2). Oto przykładowy kod:

C++C#
Python
  1. def unikalneElementy(lista):
  2.   wynik = []
  3.   for i in range(len(lista)):
  4.     dopisz = True
  5.     for j in range(i):
  6.       if (lista[i] == lista[j]):
  7.         dopisz = False
  8.         break
  9.     if (dopisz):
  10.       wynik.append(lista[i])
  11.   return wynik

Algorytm składa się z dwóch pętli: pierwsza przechodzi po kolejnych elementach tablicy wejściowej, a druga po wszystkich elementach przed aktualnie rozpatrywanym. W przypadku, gdy trafi się identyczny element pętla jest przerywana, a wartość zmiennej dopisz zmieniana na fałsz, aby element nie został dopisany. Algorytm można przyśpieszyć wyszukując identycznego elementu bezpośrednio na liście wynikowej. Niemniej pesymistyczna złożoność czasowa pozostaje taka sama.

Spójrz Wstecz

Istnieje szybka metoda znajdowania wszystkich unikalnych elementów. Najpierw dane należy posortować - jak wiadomo najlepsze algorytmy sortujące mają złożoność O(nlog(n)). Po posortowaniu identyczne elementy znajdą się koło siebie, więc przed dodaniem elementu do listy wynikowej wystarczy spojrzeć czy poprzedni element w posortowanej tablicy jest inny. Złożoność takiego przeszukania to zaledwie O(n). Oto przykładowa implementacja:

C++C#
Python
  1. def unikalneElementy(lista):
  2.   wynik = []
  3.   lista.sort()
  4.   wynik.append(lista[0])
  5.   for i in range(1, len(lista)):
  6.     if (lista[i] != lista[i - 1]):
  7.       wynik.append(lista[i])
  8.   return wynik

Jak można zauważyć algorytm uprościł się do zaledwie jednej pętlej w której znajduje się jeden warunek. Niewątpliwie jest on lepszy niż poprzednio opisany, ale pod warunkiem, że zostanie dobrany odpowiedni algorytm sortujący, ponieważ jego złożoność znacząco wpływa na efektywność napisanej funkcji.

Testowanie funkcji

W celu przetestowania napisanych funkcji wystaczy poniższy fragment programu:

C++C#
Python
  1. print("Podaj elementy tablicy:")
  2. lista = [int(x) for x in input().split()]
  3. print("Unikalne elementy to:")
  4. wynik = unikalneElementy(lista)
  5. for x in wynik:
  6.   print(x, end=' ')