Witam,
Jak w temacie, czy da się ten problem rozwiązać bez sortowania w sensownym czasie (mniejszym od n^2)?
0
0
moja kmina:
masz tablice z największymi intami (długości n), najpierw inicjujesz je możliwie najniższą wartością i potem przechodząc przez docelową tablicę, sprawdzasz każdy elementy czy czasem nie znalazłeś nowego elementu, który mógłby dojść do tej tablicy największych intów
w sumie też będzie sporo porównań, ale chyba będzie szybciej, na pewno kluczowym elementem będzie długość n (bo na każdy element z docelowej tablicy będzie maxymalnie n porównań), natomiast jeśli docelowa tablica będzie krótka, to zostanie w miarę szybko posortowana...
0
użyj QuickSort będziesz miał złożoność n logn. - a tak przecietnie 2*n logn
0
Piotrekdp napisał(a)
użyj QuickSort
efg napisał(a)
bez sortowania
...
0
oj niech sobie zrobi memcpy :D i skopiuje tablice pójdzie mu to pieronem na kopii.
0
Mógłbyś użyć nth_element(), a potem wypisać wszystkie elementy tablicy większe od niego.
0
Ja bym proponował najpierw utworzyć kopiec z n pierwszych elementów tablicy, najmniejszy element w korzeniu (można to zrobić w czasie O(n)). Potem przelatywać kolejne inty i jeśli napotkany int jest większy niż int w korzeniu to zamieniamy korzeń i napotkanego inta i poprawiamy strukturę kopca (w czasie O(lg n)). Po przeleceniu całej tablicy na początku będzie kopiec z n największych intów.
0
@donkey7 a to czasem nie będzie heapsort ? Mialo być bez sortowania ;)
0
Shalom napisał(a)
Mógłbyś użyć nth_element(), a potem wypisać wszystkie elementy tablicy większe od niego.
To nie zadziała. Skąd wiesz, że wszystkie elementy wypisane przeze mnie będą największymi elementami?
0
Jak to skąd? Jeśli wszystkich elementów w tablicy jest K i skoro (K-n)-ty najmniejszy ((K-n)-ty z kolei, gdyby sortować rosnąco) element w kolejności to jest X, to wszystkie n-1 elementów większych od niego to będzie wlasnie n-1 największych elementów (licząc z tym ustawionym na odpowiedniej pozycji przez nth_element() to będzie n ).
O ile dobrze rozumiesz co robi funkcja nth_element(). Ona sprawi ze X-ty element w tablicy będzie na takim miejscu, na jakim byłby gdyby dane były posorotowane.
0
jezeli zakres intow pozwala na stworzenie histogramu to da sie zejsc do O(n)
0
Nth element to algorytm selection, czyli "niepełny" quicksort. Od quicksorta różni go tylko to, że nie zagłębia się w partycje do których nie należy szukany element.
Mój algorytm nie jest sortowaniem. Tworzę tylko kopiec, nie sortuję nigdzie elementów po kolei. Ma gorszą złożoność oczekiwaną, ale dużo lepszą złożoność pesymistyczną (jako, że złożoność pesymistyczna algorytmu selection to O(n^2)) - no chyba, że stosują algorytm magicznych piątek, to wtedy jest rzeczywiście zawsze szybszy.
Z tym, że Nth-element (vel Selection algorithm) jest częściowym sortowaniem, a w pytaniu było napisane, że nie należy sortować.
Efg:
Sprecyzuj pytanie odnośnie powtórzeń. Co jeśli mamy ciąg: 1, 2, 2, 3, 4, 4, 5 i mamy podać trzy największe liczby? Mamy podać 3, 4, 5 czy 4, 4, 5?
cepa:
Widzę, że chcesz użyć części Counting-sorta. Idąc dalej tym tropem można wykorzystać Bucket-sorta, tzn liczyć elementy w poszczególnych kubełkach (lub Radix-sorta to prawie to samo). Wtedy mamy czas liniowy dla dowolnego stałego rozmiaru uniwersum kluczy. Tylko że to nie będzie działać, jeśli chcemy wydobyć n różnych największych intów. ATSD: N-th element ma złożoność oczekiwaną O(n).
0
zwykly najprostszy w swiecie histogram, z niego moge wyciagnanc n najwiekszych/najmniejszych intow w czasie O(n)
bedzie dzialac zarowno dla pierwszego jak i dla drugiego przypadku :P
0
Użyj magicznego algorytmu zwanego: "Algorytmem magicznych piątek" uzyskasz w ten sposób k-tą największą liczbę. Teraz wypisz wszystkie >= liczby i to chyba tyle :P
0
cepa:
OK pomyliłem się zwykły histogram taki jak z Counting sorta zadziała dla obydwu przypadków. Tyle, że inicjalizacja histogramu i późniejszy odczyt może trwać dużo dłużej niż nawet sortowanie jeśli uniwersum kluczy jest duże.
Mój algo jest bardzo łatwy do implementacji spośród podanych jeżeli nie używa się STLa. Powinien też być najszybszy jeśli wszystkie n największych intów zmieści się w cache procesora.
0
OK, faktycznie nie doczytałem co chcesz zrobić i myslałem ze sortować tym kopcem.
nth_element() korzysta z tego co wiem właśnie z magicznych piątek ;)
No ale implementowanie go samemu, bez STL faktycznie jest cięższe od kopca.