a******h
发帖数: 19 | 1 How to sort an array with only {0, 1, 2} possible values in O(n) without
extra space?
Ex: an array {0, 1, 2, 2, 1, 0} |
b*********n
发帖数: 1258 | 2 dutch national flag problme
【在 a******h 的大作中提到】
: How to sort an array with only {0, 1, 2} possible values in O(n) without
: extra space?
: Ex: an array {0, 1, 2, 2, 1, 0}
|
a******h
发帖数: 19 | 3 Thanks. Is a common question? |
g*******y
发帖数: 1930 | 4 you mean with O(1) extra space吧？直接数个数就行了吧？ |
H*M
发帖数: 1268 | 5 pretty common吧，这题还是solvable的，即使没见过。
不需要一些天外飞仙的东西
【在 a******h 的大作中提到】
: Thanks. Is a common question?
|
a******h
发帖数: 19 | 6 You still need to use three pointer to sort it.
【在 H*M 的大作中提到】
: pretty common吧，这题还是solvable的，即使没见过。
: 不需要一些天外飞仙的东西
|
c*********n
发帖数: 1057 | 7 连local variable都不能有？
我for一下也要申明个index啊
【在 a******h 的大作中提到】
: You still need to use three pointer to sort it.
|
a******h
发帖数: 19 | 8 In Java, you can only use local variable instead of pointer.
One variable for low pointer, one for mid pointer, and one for high
pointer.
【在 c*********n 的大作中提到】
: 连local variable都不能有？
: 我for一下也要申明个index啊
|
c*********n
发帖数: 1057 | 9 int lowPointer;//is it a local var or pointer?
【在 a******h 的大作中提到】
: In Java, you can only use local variable instead of pointer.
: One variable for low pointer, one for mid pointer, and one for high
: pointer.
|
m*****f
发帖数: 1243 | 10 then you need more time.
if use three pointer and swap, only read the array once.
【在 g*******y 的大作中提到】
: you mean with O(1) extra space吧？直接数个数就行了吧？
|
|
|
g*******y
发帖数: 1930 | 11 呵呵，其实我想到了这个方法的~我只是想着反正都是O(n)就随便挑个简单的
说说
【在 m*****f 的大作中提到】
: then you need more time.
: if use three pointer and swap, only read the array once.
|
H*M
发帖数: 1268 | 12 then how about [0..5]? [0..10]?
you will feel dizzy using swap.. :-)
【在 m*****f 的大作中提到】
: then you need more time.
: if use three pointer and swap, only read the array once.
|
m*****f
发帖数: 1243 | 13 hmm...seem to be a good point to discuss in the interview for possible
extension.
【在 H*M 的大作中提到】
: then how about [0..5]? [0..10]?
: you will feel dizzy using swap.. :-)
|
g*******y
发帖数: 1930 | 14 use an array of pointers
use a (at most O(1) iterations) loop to do swaps
But, anyway, in this case, the best way is just counting occurrences of each number, AKA, counting sort
【在 H*M 的大作中提到】
: then how about [0..5]? [0..10]?
: you will feel dizzy using swap.. :-)
|
H*M
发帖数: 1268 | 15 yeah. counting sort is the clean and organized way to do in this case...
each number, AKA, counting sort
【在 g*******y 的大作中提到】
: use an array of pointers
: use a (at most O(1) iterations) loop to do swaps
: But, anyway, in this case, the best way is just counting occurrences of each number, AKA, counting sort
|
