Strona główna » Algorytmy » Artykuły » Następny Największy Element
 

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(n2).

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 log2n to ostateczna złożoność algorytmu wynosi O(nlog2n) 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. }
Zadania
Zadanie 1
Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1