Вопросы Теги

массив вида размера n

если массив размера n имеет только 3 значения 0, 1 и 2 (повторил какое-либо количество раз), что лучший способ состоит в том, чтобы отсортировать их. лучше всего указывает на сложность. считайте сложность пространства и времени обоими

7
задан Gaurav Kushwaha 12 April 2010 в 12:20
поделиться

4 ответа

Подсчитайте количество появлений каждого числа и затем заполните массив правильными счетчиками, это O (n)

24
ответ дан 6 December 2019 в 06:02
поделиться

Двухстрочный Haskell: 

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
ответ дан 6 December 2019 в 06:02
поделиться

Непроверенное решение в стиле C: 

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;
2
ответ дан 6 December 2019 в 06:02
поделиться

Звучит очень похоже на проблему голландского национального флага Дейкстры.

Если вам нужно решение, которое не использует подсчет, посетите http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/

3
ответ дан 6 December 2019 в 06:02
поделиться