[lukaszwasyl]

#naukaprogramowania #cpp Pytanie - czy jeżeli wyszukujemy,przykładowo w generowanej losowo tablicy liczb drugą największą i drugą najmniejszą liczbę to konieczne jest sortowanie całej tablicy, czy można to zrobić jakoś sprytniej ? Dziękuje z góry :>

[razornfs]

@lukaszwasyl: wystarczy mieć zmienne w których trzymasz największą i drugą największą liczbę i je aktualizować iterując po tablicy

[sorhu]

@razornfs: To jest dobre jak szukasz największej czy drugiej największej. A znajdź entą największą. Wtedy zmienna czy dwie zmienne nie pomogą. Trzeba sprytniej.

No i trzeba doprecyzować definicję.
Masz 1, 1, 2.
Która liczba jest druga największa? 1 czy 2?

[razornfs]

@sorhu: odpowiadam na zadane pytanie, k-tą największa zmienną można znaleźć sortując, lub wsadzając wszystkie liczby z tablicy do min (lub max) heapa, ale zakładam że nie o to chodziło OPowi

[nargil]

http://en.cppreference.com/w/cpp/algorithm/nth_element

[GotoFinal]

no tak czy siak musisz porównać wszystkie elementy by znaleźć przed-największa, więc sortowanie wydaje się być tu idealnym rozwiązaniem, a tak to możesz zrobić zwykłe lipne wyszukiwanie, zapisujesz min/max jako 1 element z tablicy i idziesz dalej zmieniając wartości kiedy trzeba, czyli jak znajdziesz większa od max, to dajesz do max aktualną, jedyna różnica ma być taka że musisz też zapisywać poprzednią, więc zamiast zmiennych min/max masz min,prevMin,max,prevMax i zamiast zwyklego
if