jeśli tablica o rozmiarze n ma tylko 3 wartości 0, 1 i 2 (powtarzane dowolną liczbę razy), jaki jest najlepszy sposób ich sortowania. najlepiej wskazuje na złożoność. rozważyć przestrzeń i czas złożoność zarównotablica sortowania o rozmiarze n
Odpowiedz
Policz wystąpień każdego numeru, a potem wypełnić tablicę z poprawnymi liczy, to O(n)
aka Liczenie Sortowanie: http://en.wikipedia.org/wiki/Counting_sort –
sortowania typu szufladka, znany również jako sortowanie radix. – falstro
@ Andreas wartość n może być dość duża, więc zliczanie może być nieco kłopotliwe w niektórych przypadkach –
dźwięku dużo jak Dijkstry Dutch National Flag problem.
Jeśli potrzebne jest rozwiązanie, które nie używają liczenia, sprawdź http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/
Nietestowane rozwiązanie C-style:
int count[3] = {0, 0, 0};
for (int i = 0; i < n; ++i)
++count[array[i]];
int pos = 0;
for (int c = 0; c < 3; ++c)
for (int i = array[c]; i; --i)
array[pos++] = c;
"unsigned" lub "size_t" będą bardziej odpowiednie. – GManNickG
Haskell dwa-liner:
count xs = Map.toList $ Map.fromListWith (+) [ (x, 1) | x <- xs ]
countingSort xs = concatMap (\(x, n) -> replicate n x) (count xs)
> countingSort [2,0,2,1,2,2,1,0,2,1]
[0,0,1,1,1,2,2,2,2,2]
- 1. Const char tablica o rozmiarze szablon argumentu vs. wskaźnik char
- 2. m liczb całkowitych brakujących w tablicy o rozmiarze n
- 3. Klasa - Zdefiniowana przez użytkownika inteligentna tablica o rozmiarze dynamicznym
- 4. An (n) algorytm sortowania
- 5. Dla danych wejściowych o rozmiarze n, dla których wartości n powoduje wstawianie-sortowanie bitowe-sortowanie?
- 6. std :: array o rozmiarze zero
- 7. Tablica sortowania Androida
- 8. Tablica sortowania ruby tablicy
- 9. Tablica sortowania AngularJS ngOptions
- 10. Podział listy na mniejsze listy o rozmiarze N
- 11. Tworzenie macierzy o rozmiarze n podczas tworzenia JSLinta?
- 12. n-wymiarowa tablica
- 13. Znajdź, czy tablica jest sekwencją w czasie O (n) i O (1)
- 14. Czy to prawda, że ciągi sortowania to O (n^2logn)?
- 15. Bitset o zmiennym rozmiarze
- 16. wektor o stałym rozmiarze
- 17. Czy istnieje funkcja podziału dużej ramki danych na n mniejszych ramek danych o równym rozmiarze (według wierszy) i mają one ramkę danych n + 1 o mniejszym rozmiarze?
- 18. Wymiana „\ r \ n” o „\ n”
- 19. PHP podwójna tablica sortowania na podstawie podłańcucha
- 20. Tablica sortowania JavaScript obiektów według właściwości boolowskiej
- 21. Tablica wielowymiarowa sortowania PHP według daty
- 22. sortowania int tablica z tylko 3 elementy
- 23. indeksowi n Tablica wymiarową z (n-1) d tablicy
- 24. Tablica sortowania javascript z mieszanymi ciągami znaków i wartościami pustymi
- 25. Dlaczego sortowanie jest ciągiem O (n log n)?
- 26. Tablica numpy, która jest (n, 1) i (n,)
- 27. Czy istnieje skrótowe oznaczenie O (n log n)?
- 28. Zmiana O (n^3) na O (n^2) w JavaScript
- 29. Dlaczego TreeSet Iteracja O (n) zamiast O (n * logn)?
- 30. Jaki jest najskuteczniejszy sposób konwersji Matrycy {T} o rozmiarze 1 * N lub N * 1 w Julii na wektor {T}?
Co robi najlepiej znaczy w tym przypadku? – EvilTeach
Zależy od tego, co masz na myśli przez "najlepszy" - najwygodniejszy? najszybszy ? najbardziej wydajne pod względem przechowywania? najbardziej przenośny? –