Wspólne Elementy Trzech Tablic

Zadanie

Dane są trzy posortowane tablice liczb całkowitych. Zadanie polega na znalezieniu wszystkich liczb, które występująca na każdej z trzech tablic. Innymi słowy należy znaleźć przecięcie trzech tablic. Zakładamy, że tablice nie mają powtarzających się elementów.

Przykładowo dla następujących tablic:

1. 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30
2. 3 6 9 12 15 18 21 24 27 30
3. 4 8 12 16 20 24 28 32

Program powinien zwrócić, że powtarzającymi się elementami we wszystkich tablicach są elementy 12 oraz 24.

Rozwiązanie

Algorytm

W celu rozwiązania powyższego zadania w czasie liniowym należy zadeklarować trzy indeksy i₁, i₂ i i₃. Po jednym dla każdej tablicy. Następnie jeśli pod wskazanymi indeksami jest ta sama wartość to wszystkie indeksy należy zwiększyć. Jeśli jednak są różne wartości to: indeks i₁ zostaje zwiększony, gdy element i₁ pierwszej tablicy jest mniejszy od elementu na pozycji i₂ w drugiej tablicy. Analogicznie należy postąpić dla tablicy drugiej i trzeciej. Z kolei indeks trzeciej tablicy jest zwiększany, gdy nie są spełnione dwa wcześniejsze warunki. Algorytm kończy działanie, gdy k-ty indeks wykroczy poza granice k-tej tablicy.

Przykład

Dane są następujące tablice:

1. 1 3 5 7 9 12
2. 3 4 5 12
3. 3 6 9 12 15

Program wykona następujące operacje:

W podanych tablicach znalezione zostały tylko dwa powtarzające się elementy: 3 oraz 12.

Implementacja

Oto przykładowa implementacja funkcji znajdzWspolneElementy(). Funkcja nie zwraca żadnej wartości, ponieważ znalezione przecięcie tablic wypisuje bezpośrednio na konsole.

1. static void znajdzWspolneElementy(int[] tab1, int[] tab2, int[] tab3) {
2.   int i1 = 0, i2 = 0, i3 = 0;
3.   while (i1 < tab1.Length && i2 < tab2.Length && i3 < tab3.Length) {
4.     if (tab1[i1] == tab2[i2] && tab1[i1] == tab3[i3]) {
5.       Console.Write("{0} ", tab1[i1]);
6.       i1++;
7.       i2++;
8.       i3++;
9.     } else {
10.       if (tab1[i1] < tab2[i2]) {
11.         i1++;
12.       } else if (tab2[i2] < tab3[i3]) {
13.         i2++;
14.       } else {
15.         i3++;
16.       }
17.     }
18.   }
19. }

(2.) Przygotuj indeksy, a następnie (3.) rozpocznij wyszukiwanie w pętli, aż w której z tablic zabraknie elementów. (4.) Jeśli zostanie znaleziony element we wszystkich tablicach to: (5.) wypisz go i (6. - 8.) zwiększ wszystkie indeksy. (9.) Jednak w przeciwnym przypadku (10. - 16.) zwiększ odpowiedni indeks.

Testowanie funkcji

Oto przykładowy kod, który wczyta od użytkownika wszystkie tablice, a następnie wywoła funkcję poszukującą przecięcia trzech tablic.

1. static int[] wczytajTablice(int nr) {
2.   Console.WriteLine("Poda element tablicy {0}:", nr);
3.   string[] str = Console.ReadLine().Split(' ');
4.   int[] tab = new int[str.Length];
5.   for (int i = 0; i < str.Length; i++)
6.     tab[i] = Convert.ToInt32(str[i]);
7.   return tab;
8. }
10. static void Main(string[] args) {
11.   int[] tab1 = wczytajTablice(1);
12.   int[] tab2 = wczytajTablice(2);
13.   int[] tab3 = wczytajTablice(3);
14.   znajdzWspolneElementy(tab1, tab2, tab3);
15.   Console.ReadKey();
16. }

• Kod źródłowy Implementacja