Как стать автором
Обновить

Комментарии 4

We also can count three counters on the first pass and fill the right values on the second pass.

Let me check if I got the idea.


Let's say we have [1, 2, 1, 0]
In the first pass, we count the number of occurrences for zeroes, ones and twos:


0:0, 1:2, 2:1


And in the second run, we restore the array. Did I get the idea?


If I understood you correctly, then the described algorithm does not work in-place, right?


EDIT: I noted that my post doesn't emphasize that the provided solution works in-place. Thanks for the remark, updated the article.

Counters will be 0:1, 1:2, 2:1.
And then we just overwrite our existing array so this algorithm will work in place too.

Thanks, got it.

Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории