Комментарии 4
We also can count three counters on the first pass and fill the right values on the second pass.
+1
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.
0
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.
And then we just overwrite our existing array so this algorithm will work in place too.
+1
Зарегистрируйтесь на Хабре , чтобы оставить комментарий
Algorithms in Go: Dutch National Flag