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. int * NastepnyWiekszy(int * dane, int n) {
2.   int * wynik = new int[n];
3.   for (int i = 0; i < n; i++) {
4.     int max = -1;
5.     for (int j = i; j < n; j++) {
6.       if (dane[i] < dane[j]) {
7.         max = dane[j];
8.         break;
9.       }
10.     }
11.     wynik[i] = max;
12.   }
13.   return wynik;
14. }

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. int * NastepnyWiekszy(int * dane, int n) {
2.   int * wynik = new int[n];
3.   priority_queue<para, vector<para>, greater<para>> kolejka;
4.   for (int i = 0; i < n; i++) {
5.     while (kolejka.size() != 0) {
6.       para porownaj = kolejka.top();
7.       if (porownaj.first < dane[i]) {
8.         kolejka.pop();
9.         wynik[porownaj.second] = dane[i];
10.       }
11.       else {
12.         break;
13.       }
14.     }
15.     kolejka.push(make_pair(dane[i], i));
16.   }
17.   while (kolejka.size() != 0) {
18.     para teraz = kolejka.top();
19.     kolejka.pop();
20.     wynik[teraz.second] = -1;
21.   }
22.   return wynik;
23. }

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. int main () {
2.   int n;
3.   cout << "Ile tablica ma liczb?\n n = ";
4.   cin >> n;
5.   cout << "Podaj liczb(y):\n";
6.   int * dane = new int[n];
7.   for (int i = 0; i < n; i++) {
8.     cin >> dane[i];
9.   }
10.   int * wynik = NastepnyWiekszy(dane, n);
11.   for (int i = 0; i < n; i++) {
12.     cout << dane[i] << "\t> " << wynik[i] << endl;
13.   }
14.   system("pause");
15.   return 0;
16. }

• Kod źródłowy Implementacja