Następny Największy Element

Zadanie

Dana jest tablica liczb całkowitych na której elementy nie są w żaden sposób uporządkowane. Napisz program, który dla każdego elementu wyznaczy element większy w dalszej części tablicy niż on sam. Jeśli nie istnieje wypisz -1.

Przykład

Przykładowo jest dana tablica liczb [5, 4, 10, 2, 7, 1]. Wynikiem działania algorytmu powinna być tablica [10, 10, -1, 7, -1, -1]. Wynika to z faktu, że największy element po 5 to 10. Podobnie dla liczby 4. Z kolei 10 nie ma większej wartości występującej po niej, więc oznaczamy to wartością -1. Te same zasady dotyczą ostatnich trzech liczb, ale tylko 2 ma większą liczbę na prawo i jest to 7.

Implementacja

Rozwiązanie Proste

Zadanie można rozwiązać algorytmem, który dla każdego elementu listy przejrzy elementy w dalszej części. Oto przykłoadyw kod realizujący to:

1. static int[] NastepnyWiekszy(int[] dane)
2. {
3.   int[] wynik = new int[dane.Length];
4.   for (int i = 0; i < dane.Length; i++)
5.   {
6.     int max = -1;
7.     for (int j = i; j < dane.Length; j++)
8.     {
9.       if (dane[i] < dane[j])
10.       {
11.         max = dane[j];
12.         break;
13.       }
14.     }
15.     wynik[i] = max;
16.   }
17.   return wynik;
18. }

Rozwiązanie składa się z dwóch pętli. Najgorszym przypadkiem jest tablica liczb w kolejności malejącej - wtedy dla i-tego elementu trzeba sprawdzić n - i - 1 dalszych liczb. Jest to złożoność identyczna z sortowaniem bąbelkowym, a więc złożoność algorytmu jest kwadratowa O(n²).

Implementacja

Rozwiązanie Optymalne

Poprzedni algorytm można usprawnić. Można to zrobić poprzez optymalizację procesu wyszukiwania. Otóż należy utworzyć dodatkową kolejkę w której będą przechowywane jeszcze nie opisane liczby. Bardzo ważne jest to, aby kolejka ta była automatycznie sortowana po wartościach elementu, a więc trzeba pamiętać parę wartość x indeks, aby później można się było odwołać do odpowiedniej pozycji. Jeśli kolejka nie jest pusta to sprawdzamy czy aktualny element jest większy od jakiegokolwiek w kolejce. Jeśli tak to należy wpisać aktualny element jako element od nich większy.

Oto przykładowy kod:

1. static int[] NastepnyWiekszy(int[] dane)
2. {
3.   int[] wynik = new int[dane.Length];
4.   SortedList<int, int> kolejka = new SortedList<int, int>();
5.   for (int i = 0; i < dane.Length; i++)
6.   {
7.     while (kolejka.Count != 0)
8.     {
9.       int wartosc = kolejka.Keys[0];
10.       int indeks = kolejka[wartosc];
11.       if (wartosc < dane[i])
12.       {
13.         wynik[indeks] = dane[i];
14.         kolejka.RemoveAt(0);
15.       }
16.       else
17.       {
18.         break;
19.       }
20.     }
21.     kolejka.Add(dane[i], i);
22.   }
23.   while (kolejka.Count != 0)
24.   {
25.     int wartosc = kolejka.Keys[0];
26.     int indeks = kolejka[wartosc];
27.     kolejka.RemoveAt(0);
28.     wynik[indeks] = -1;
29.   }
30.   return wynik;
31. }

Przyjmując, że tablica składa się z n elementów, a wstawienie elementu do kolejki jest log₂n to ostateczna złożoność algorytmu wynosi O(nlog₂n) co jest znacząco szybsze od złożoności kwadratowej.

Testowanie funkcji

Wybrane rozwiązanie można przetestować poprzez przykładowy kod poniżej, który wczyta tablicę, a następnie wypisze wynik.

1. static void Main(string[] args)
2. {
3.   Console.Write("Podaj liczb(y):\n");
4.   string[] surowe = Console.ReadLine().Split(' ');
5.   int[] dane = new int[surowe.Length];
6.   for (int i = 0; i < dane.Length; i++)
7.   {
8.     dane[i] = Convert.ToInt32(surowe[i]);
9.   }
10.   int[] wynik = NastepnyWiekszy(dane);
11.   for (int i = 0; i < wynik.Length; i++)
12.   {
13.     Console.WriteLine("{0}\t> {1}", dane[i], wynik[i]);
14.   }
15.   Console.ReadKey();
16. }

• Kod źródłowy Implementacja