Brakujące Elementy

Zadanie

Dane są dwie tablice posortowanych liczb. Liczby zapisane w tablicach mogą się powtarzać. Zadanie polega na zliczeniu ile liczb z obydwu tablic nie ma swojego odpowiednika w drugiej tablicy.

Weźmy przykładowo tablicę {1, 2, 3, 5} oraz {2, 2, 3, 4, 5}. Jedynie 2, 3, 5 mają swoje odpowiedniki w drugiej tablicy niż one same. Oznacza to, że tablice różnią się trzema elementami.

Analiza zadania

Najprostszy algorytm, które pozwoli rozwiązać to zadanie brzmi następująco: pobierz pierwszy element z tablicy 1 i wyszukaj go w tablicy 2. Jeśli istnieje to usuń go. W przeciwnym razie zwiększ licznik różnych elementów. Nie byłby to jednak najefektywniejszy algorytm, ponieważ jego złożoność wynosi O(n₁n₂) co dla tablic o zbliżonej długości daje złożoność kwadratową. Algorytm można zoptymalizować, ponieważ nie została wykorzystana informacja o tym, że tablice są posortowane. Wykorzystanie wyszukiwania binarnego pozwoliłoby na zmniejszenie złożoności do O(nlog(n)), ale nie jest najlepsze możliwe rozwiązanie.

Algorytm można napisać tak, aby miał złożoność liniową O(n). Algorytm rozpoczynamy od ustalenia indeksów dla każdej tablicy na 0. Następnie porównujemy elementy aktualnie wskazywane przez indeksy. Jeśli elementy są identyczne to zwiększamy obydwa indeksy. Jednak jeśli elementy są różne to zwiększamy licznik różnych elementów, a następnie zwiększamy indeks dla tablicy, która ma mniejszy element. Proces ten powtarzamy, aż w którejś tablicy nie będzie więcej elementów.

Przykład

Rozpatrzmy ponownie dwie tablice {1, 2, 3, 5} oraz {2, 2, 3, 4, 5}. Kolejno zostaną wykonane następujące operacje:

W tym przypadku obydwa indeksy przekraczają długości tablic równocześnie. Ostatecznie pomiędzy tablicami istnieją dokładnie 3 różne elementy.

Implementacja

Poniżej znajduje się przykładowa implementacja funkcji ileBrakujacychElementow(), która dla podanych dwóch tablic sprawdza ile jest różnych elementów.

1. static int ileBrakujacychElementow(List<int> tab1, List<int> tab2) {
2.   int i1 = 0, i2 = 0;
3.   int brakujacych = 0;
4.   while (i1 < tab1.Count && i2 < tab2.Count) {
5.     if (tab1[i1] == tab2[i2]) {
6.       i1++;
7.       i2++;
8.     } else {
9.       brakujacych++;
10.       if (tab1[i1] > tab2[i2]) {
11.         i2++;
12.       } else {
13.         i1++;
14.       }
15.     }
16.   }
17.   brakujacych += tab1.Count - i1;
18.   brakujacych += tab2.Count - i2;
19.   return brakujacych;
20. }

Kolejne pary elementów są porównywane. Dla takich samych elementów zwiększane są oba indeksy i1 oraz i2, ale dla różnych zwiększany jest licznik brakujących elementów, a następnie odpowiedni indeks tj. tej tablicy, której element jest mniejszy. Na koniec bardzo ważne jest, aby pamiętać, że któraś tablica może wciąż posiadać elementy do sprawdzenia, więc należy je dodać jako elementy brakujące!

Testowanie funkcji

Do przetestowania kodu można skorzystać z poniższego fragmentu kodu, który wczytuje od użytkownika potrzebne dane, a następnie wypisuje na ekran ile jest brakujących elementów:

1. static void Main(string[] args) {
2.   List<int> tab1 = new List<int>();
3.   List<int> tab2 = new List<int>();
4.   wczytajListe(ref tab1, 1);
5.   wczytajListe(ref tab2, 2);
6.   int wynik = ileBrakujacychElementow(tab1, tab2);
7.   Console.WriteLine("Brakuje {0} elementów", wynik);
8.   Console.ReadKey();
9. }

• Kod źródłowy Implementacja