NIW-RFE-09.28~~~~~~~~~~~~~~~~~~~~~~~~~~# Immigration - 落地生根
k*r
1 楼
一个记录数组，每个记录的关键字是0，1，2三个数中的一种，
要求将数组按关键字排序。要求算法是稳定排序，O(n)时间，常数空间。
哪位同学说说怎么做？
要求将数组按关键字排序。要求算法是稳定排序，O(n)时间，常数空间。
哪位同学说说怎么做？
f*D
2 楼
Just find out my case status changed
7.6 efile 140
9.28 RFE sent out
Not sure the RFE contents.
Any one wants to work together?
Thanks.
7.6 efile 140
9.28 RFE sent out
Not sure the RFE contents.
Any one wants to work together?
Thanks.
H*r
3 楼
bucket?
【在 k*******r 的大作中提到】
: 一个记录数组，每个记录的关键字是0，1，2三个数中的一种，
: 要求将数组按关键字排序。要求算法是稳定排序，O(n)时间，常数空间。
: 哪位同学说说怎么做？
【在 k*******r 的大作中提到】
: 一个记录数组，每个记录的关键字是0，1，2三个数中的一种，
: 要求将数组按关键字排序。要求算法是稳定排序，O(n)时间，常数空间。
: 哪位同学说说怎么做？
c*g
4 楼
bless
【在 f****D 的大作中提到】
: Just find out my case status changed
: 7.6 efile 140
: 9.28 RFE sent out
: Not sure the RFE contents.
: Any one wants to work together?
: Thanks.
【在 f****D 的大作中提到】
: Just find out my case status changed
: 7.6 efile 140
: 9.28 RFE sent out
: Not sure the RFE contents.
: Any one wants to work together?
: Thanks.
k*r
5 楼
具体点？ 主要是常数空间和稳定排序这两个要求常常互相抵触
【在 H****r 的大作中提到】
: bucket?
【在 H****r 的大作中提到】
: bucket?
b*r
6 楼
又不提啥建议，光BLESS干啥？
【在 c******g 的大作中提到】
: bless
【在 c******g 的大作中提到】
: bless
w*o
7 楼
counting sort?
【在 k*******r 的大作中提到】
: 一个记录数组，每个记录的关键字是0，1，2三个数中的一种，
: 要求将数组按关键字排序。要求算法是稳定排序，O(n)时间，常数空间。
: 哪位同学说说怎么做？
【在 k*******r 的大作中提到】
: 一个记录数组，每个记录的关键字是0，1，2三个数中的一种，
: 要求将数组按关键字排序。要求算法是稳定排序，O(n)时间，常数空间。
: 哪位同学说说怎么做？
k*w
8 楼
收到后看写的什么
p*2
9 楼
int[] counts=new int[3];
j*a
10 楼
background?
【在 f****D 的大作中提到】
: Just find out my case status changed
: 7.6 efile 140
: 9.28 RFE sent out
: Not sure the RFE contents.
: Any one wants to work together?
: Thanks.
【在 f****D 的大作中提到】
: Just find out my case status changed
: 7.6 efile 140
: 9.28 RFE sent out
: Not sure the RFE contents.
: Any one wants to work together?
: Thanks.
Z*Z
11 楼
好像有问题，再想想
【在 k*******r 的大作中提到】
: 具体点？ 主要是常数空间和稳定排序这两个要求常常互相抵触
【在 k*******r 的大作中提到】
: 具体点？ 主要是常数空间和稳定排序这两个要求常常互相抵触
c*g
12 楼
小弟实在是没啥主意啊
【在 b*********r 的大作中提到】
: 又不提啥建议，光BLESS干啥？
【在 b*********r 的大作中提到】
: 又不提啥建议，光BLESS干啥？
k*r
13 楼
我觉得应该是 counting sort的思路，但题目没允许有一个额外的输出数组，所以要常
数空间就得在原输入数组中swap 操作，但这样一swap又无法保持是稳定排序。
【在 Z*****Z 的大作中提到】
: 好像有问题，再想想
数空间就得在原输入数组中swap 操作，但这样一swap又无法保持是稳定排序。
【在 Z*****Z 的大作中提到】
: 好像有问题，再想想
e*r
14 楼
先把rfe贴来看看再说.NIW的RFE通常不太难过,表太担心.
板上不最近还有一个嘛.
祝好运
【在 f****D 的大作中提到】
: Just find out my case status changed
: 7.6 efile 140
: 9.28 RFE sent out
: Not sure the RFE contents.
: Any one wants to work together?
: Thanks.
板上不最近还有一个嘛.
祝好运
【在 f****D 的大作中提到】
: Just find out my case status changed
: 7.6 efile 140
: 9.28 RFE sent out
: Not sure the RFE contents.
: Any one wants to work together?
: Thanks.
g*e
15 楼
the dutch flag problem
search google
search google
k*r
16 楼
赫赫，这应该是正解了，多谢，赞知识广博
【在 g*********e 的大作中提到】
: the dutch flag problem
: search google
【在 g*********e 的大作中提到】
: the dutch flag problem
: search google
w*o
17 楼
我觉得 你说的不对。
你去研究一下，DNF不是stable,因为它跟quicksort如出一辙，都不是stable的。
【在 g*********e 的大作中提到】
: the dutch flag problem
: search google
你去研究一下，DNF不是stable,因为它跟quicksort如出一辙，都不是stable的。
【在 g*********e 的大作中提到】
: the dutch flag problem
: search google
p*2
18 楼
难道 int[3]不算常数空间吗？
k*r
19 楼
恩，仔细看了看，好像wiki 上DNF给出的排序方法确实是不稳定的，还是有问题啊
【在 w****o 的大作中提到】
: 我觉得 你说的不对。
: 你去研究一下，DNF不是stable,因为它跟quicksort如出一辙，都不是stable的。
【在 w****o 的大作中提到】
: 我觉得 你说的不对。
: 你去研究一下，DNF不是stable,因为它跟quicksort如出一辙，都不是stable的。
k*r
20 楼
int[3]当然算常数空间，不过具体你的解法是怎样的呢
【在 p*****2 的大作中提到】
: 难道 int[3]不算常数空间吗？
【在 p*****2 的大作中提到】
: 难道 int[3]不算常数空间吗？
p*2
21 楼
不好意思。没好好看。还以为是前边一道题呢。
【在 k*******r 的大作中提到】
: int[3]当然算常数空间，不过具体你的解法是怎样的呢
k*r
22 楼
BTW, 这是facebook 给俺的电面题，让俺非常郁闷
p*2
23 楼
就这一道题吗？
【在 k*******r 的大作中提到】
: BTW, 这是facebook 给俺的电面题，让俺非常郁闷
k*r
24 楼
电面嘛，就这一题。我20分钟没做出来，就和对方直接拜拜了
【在 p*****2 的大作中提到】
:
: 就这一道题吗？
【在 p*****2 的大作中提到】
:
: 就这一道题吗？
p*2
25 楼
啊？我的经验都是两题，第一题容易，第二题稍难。你申请的什么职位呀？
【在 k*******r 的大作中提到】
: 电面嘛，就这一题。我20分钟没做出来，就和对方直接拜拜了
k*r
26 楼
就问了我这一道题，题目和职位没关系把？
（不过我在简历中确实吹过自己是算法expert,难道因为这个... 汗）
（不过我在简历中确实吹过自己是算法expert,难道因为这个... 汗）
p*2
27 楼
那你最后怎么答的？
【在 k*******r 的大作中提到】
: 就问了我这一道题，题目和职位没关系把？
: （不过我在简历中确实吹过自己是算法expert,难道因为这个... 汗）
k*r
28 楼
我答出的要么不稳定，要么不是常数空间，就这么纠缠了 20 分钟
P*U
29 楼
没搞明白为啥counting sort不行啊？
p*2
30 楼
数组里是纪录，不是整数。
【在 P*******U 的大作中提到】
: 没搞明白为啥counting sort不行啊？
C*U
31 楼
不stable吧
时间是O(n) 空间是O(3)对的
【在 P*******U 的大作中提到】
: 没搞明白为啥counting sort不行啊？
时间是O(n) 空间是O(3)对的
【在 P*******U 的大作中提到】
: 没搞明白为啥counting sort不行啊？
z*n
32 楼
我也想问问这题怎么解？
Amazon电面的时候也问过类似的问题，一个数组，包含positive，negative, zero 三
种数，要求按照 positive，zero, negative 排序，而且不能改变原记录的相对次序，
O(1)空间。
Dutch flag ship Time-O(n), Space-O(1), 但不是稳定的
我只做出一个O(n^2)的，于是没搞定。
Amazon电面的时候也问过类似的问题，一个数组，包含positive，negative, zero 三
种数，要求按照 positive，zero, negative 排序，而且不能改变原记录的相对次序，
O(1)空间。
Dutch flag ship Time-O(n), Space-O(1), 但不是稳定的
我只做出一个O(n^2)的，于是没搞定。
m*n
33 楼
public static void dutch(int[] A, int size) {
int low =0, mid = 0, high=size-1;
while(low
while(high>=0 && A[high]==2)
high--;
mid = low;
//invariants : [0,low) ----> 0
// [low,mid) ---> 1
// [mid, high] ---> unknown
// (high, size-1] ---> 2
while(mid<=high) {
if(A[mid]==0) {
swap(A,mid,low);
low++;
mid++;
}
else if(A[mid]==1) {
mid++;
}
else { //equals to 2
swap(A,high,mid);
high--;
}
}
}
int low =0, mid = 0, high=size-1;
while(low
while(high>=0 && A[high]==2)
high--;
mid = low;
//invariants : [0,low) ----> 0
// [low,mid) ---> 1
// [mid, high] ---> unknown
// (high, size-1] ---> 2
while(mid<=high) {
if(A[mid]==0) {
swap(A,mid,low);
low++;
mid++;
}
else if(A[mid]==1) {
mid++;
}
else { //equals to 2
swap(A,high,mid);
high--;
}
}
}
z*n
34 楼
这个dutch也不是稳定的
【在 m***n 的大作中提到】
: public static void dutch(int[] A, int size) {
: int low =0, mid = 0, high=size-1;
: while(low
: while(high>=0 && A[high]==2)
: high--;
: mid = low;
: //invariants : [0,low) ----> 0
: // [low,mid) ---> 1
: // [mid, high] ---> unknown
【在 m***n 的大作中提到】
: public static void dutch(int[] A, int size) {
: int low =0, mid = 0, high=size-1;
: while(low
: while(high>=0 && A[high]==2)
: high--;
: mid = low;
: //invariants : [0,low) ----> 0
: // [low,mid) ---> 1
: // [mid, high] ---> unknown
s*n
35 楼
好了，终于想出来了：
第一遍：count0，1，2的个数l, m, n
第二遍：根据l,m,n很容易确定每个元素最终要挪到哪个位置，把数组元素值改成最终
目的地的下标
第三遍：根据a[i]!=i的条件进行swap到最终位置
第四遍：根据l,m,n恢复数组元素值为0,1,2
第一遍：count0，1，2的个数l, m, n
第二遍：根据l,m,n很容易确定每个元素最终要挪到哪个位置，把数组元素值改成最终
目的地的下标
第三遍：根据a[i]!=i的条件进行swap到最终位置
第四遍：根据l,m,n恢复数组元素值为0,1,2
s*n
36 楼
Data a[size];
...
int l=0,m=0;
for (int i=0; i
else if (a[i].key==1) m++;
else n++;
}
int aidx = 0;
int bidx = 0;
int cidx = 0;
for (int i=0; i
a[i].key = aidx++;
} else if (a[i].key==1) {
a[i].key = l + bidx++;
} else {
a[i].key = l + m + cidx++;
}
}
for (int i=0; i
int swapIdx = a[i];
Data tmp = a[swapIdx];
a[swapIdx] = a[i];
a[i] = tmp;
}
}
for (int i=0; i
...
int l=0,m=0;
for (int i=0; i
else if (a[i].key==1) m++;
else n++;
}
int aidx = 0;
int bidx = 0;
int cidx = 0;
for (int i=0; i
a[i].key = aidx++;
} else if (a[i].key==1) {
a[i].key = l + bidx++;
} else {
a[i].key = l + m + cidx++;
}
}
for (int i=0; i
int swapIdx = a[i];
Data tmp = a[swapIdx];
a[swapIdx] = a[i];
a[i] = tmp;
}
}
for (int i=0; i
H*r
37 楼
看错题了， 还以为是数组里存的是0，1，2呢，关键字是0，1，2的话就是Dutch
national flag problem
【在 k*******r 的大作中提到】
: 一个记录数组，每个记录的关键字是0，1，2三个数中的一种，
: 要求将数组按关键字排序。要求算法是稳定排序，O(n)时间，常数空间。
: 哪位同学说说怎么做？
national flag problem
【在 k*******r 的大作中提到】
: 一个记录数组，每个记录的关键字是0，1，2三个数中的一种，
: 要求将数组按关键字排序。要求算法是稳定排序，O(n)时间，常数空间。
: 哪位同学说说怎么做？
i*7
38 楼
int cnt[3] = {0,0,0};
for(int i = 0; i
for(int i = 0; i < cnt[0]; i++)
a[i] = 0;
for(int i = 0; i < cnt[1]; i++)
a[i + cnt[0]] = 1;
for(int i = 0; i < cnt[2]; i++)
a[i + cnt[0] + cnt[1]] = 2;
for(int i = 0; i
for(int i = 0; i < cnt[0]; i++)
a[i] = 0;
for(int i = 0; i < cnt[1]; i++)
a[i + cnt[0]] = 1;
for(int i = 0; i < cnt[2]; i++)
a[i + cnt[0] + cnt[1]] = 2;
s*n
39 楼
Dutch national flag只能保证middle的不打乱，up和low部分全搞乱
【在 H****r 的大作中提到】
: 看错题了， 还以为是数组里存的是0，1，2呢，关键字是0，1，2的话就是Dutch
: national flag problem
【在 H****r 的大作中提到】
: 看错题了， 还以为是数组里存的是0，1，2呢，关键字是0，1，2的话就是Dutch
: national flag problem
k*r
40 楼
呵呵，感觉这个解法虽然正确，但不是正解，因为万一要求关键字是只能为0,1,2 的
枚举类型，就不能这样干了
【在 s******n 的大作中提到】
: Data a[size];
: ...
: int l=0,m=0;
: for (int i=0; i
: else if (a[i].key==1) m++;
: else n++;
: }
: int aidx = 0;
: int bidx = 0;
枚举类型，就不能这样干了
【在 s******n 的大作中提到】
: Data a[size];
: ...
: int l=0,m=0;
: for (int i=0; i
: else if (a[i].key==1) m++;
: else n++;
: }
: int aidx = 0;
: int bidx = 0;
t*e
41 楼
I think all above solutions have issues. Can we solve a simplified problem
with just 1 and 2 first with pure swap? Assume each
record has a number and it is not modifiable.
struct record {
const int value;
const int key; //key is just 1 and 2
};
sort(vector a)
{
//fill in.
}
with just 1 and 2 first with pure swap? Assume each
record has a number and it is not modifiable.
struct record {
const int value;
const int key; //key is just 1 and 2
};
sort(vector
{
//fill in.
}
S*t
42 楼
要求只是说 “要求将数组按关键字排序”
也就是说排序的标准只是关键字而已
【在 s******n 的大作中提到】
: Dutch national flag只能保证middle的不打乱，up和low部分全搞乱
也就是说排序的标准只是关键字而已
【在 s******n 的大作中提到】
: Dutch national flag只能保证middle的不打乱，up和low部分全搞乱
k*r
43 楼
没这么简单。数组记录还有其他内容，只是关键字是1，2，3
【在 i*********7 的大作中提到】
: int cnt[3] = {0,0,0};
: for(int i = 0; i
: for(int i = 0; i < cnt[0]; i++)
: a[i] = 0;
: for(int i = 0; i < cnt[1]; i++)
: a[i + cnt[0]] = 1;
: for(int i = 0; i < cnt[2]; i++)
: a[i + cnt[0] + cnt[1]] = 2;
【在 i*********7 的大作中提到】
: int cnt[3] = {0,0,0};
: for(int i = 0; i
: for(int i = 0; i < cnt[0]; i++)
: a[i] = 0;
: for(int i = 0; i < cnt[1]; i++)
: a[i + cnt[0]] = 1;
: for(int i = 0; i < cnt[2]; i++)
: a[i + cnt[0] + cnt[1]] = 2;
k*r
44 楼
题目要求了必须是稳定排序，也就是关键字相同时原有顺序不能打乱
【在 S***t 的大作中提到】
: 要求只是说 “要求将数组按关键字排序”
: 也就是说排序的标准只是关键字而已
【在 S***t 的大作中提到】
: 要求只是说 “要求将数组按关键字排序”
: 也就是说排序的标准只是关键字而已
z*n
45 楼
好办法，不错！
不过，这种方法，平均情况好像是O(n^2)的，可能第三部要swap n次才能swap到合适位
置；
另外，对关键词0，1，2这种情况行，因为可以恢复；
如果是关键字是正数、0、负数，按照 >0, =0, <0 进行分，感觉就不行了，最后没法
恢复。
【在 s******n 的大作中提到】
: 好了，终于想出来了：
: 第一遍：count0，1，2的个数l, m, n
: 第二遍：根据l,m,n很容易确定每个元素最终要挪到哪个位置，把数组元素值改成最终
: 目的地的下标
: 第三遍：根据a[i]!=i的条件进行swap到最终位置
: 第四遍：根据l,m,n恢复数组元素值为0,1,2
不过，这种方法，平均情况好像是O(n^2)的，可能第三部要swap n次才能swap到合适位
置；
另外，对关键词0，1，2这种情况行，因为可以恢复；
如果是关键字是正数、0、负数，按照 >0, =0, <0 进行分，感觉就不行了，最后没法
恢复。
【在 s******n 的大作中提到】
: 好了，终于想出来了：
: 第一遍：count0，1，2的个数l, m, n
: 第二遍：根据l,m,n很容易确定每个元素最终要挪到哪个位置，把数组元素值改成最终
: 目的地的下标
: 第三遍：根据a[i]!=i的条件进行swap到最终位置
: 第四遍：根据l,m,n恢复数组元素值为0,1,2
z*4
46 楼
这个swap的step应该是O(n)吧，找和自己value做index
【在 z*****n 的大作中提到】
: 好办法，不错！
: 不过，这种方法，平均情况好像是O(n^2)的，可能第三部要swap n次才能swap到合适位
: 置；
: 另外，对关键词0，1，2这种情况行，因为可以恢复；
: 如果是关键字是正数、0、负数，按照 >0, =0, <0 进行分，感觉就不行了，最后没法
: 恢复。
【在 z*****n 的大作中提到】
: 好办法，不错！
: 不过，这种方法，平均情况好像是O(n^2)的，可能第三部要swap n次才能swap到合适位
: 置；
: 另外，对关键词0，1，2这种情况行，因为可以恢复；
: 如果是关键字是正数、0、负数，按照 >0, =0, <0 进行分，感觉就不行了，最后没法
: 恢复。
H*r
47 楼
If stable sorting desired then it's getting complicated. There's some
article on this:
"Stable minimum space partitioning in linear time"
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.25.555
【在 k*******r 的大作中提到】
: 没这么简单。数组记录还有其他内容，只是关键字是1，2，3
article on this:
"Stable minimum space partitioning in linear time"
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.25.555
【在 k*******r 的大作中提到】
: 没这么简单。数组记录还有其他内容，只是关键字是1，2，3
H*r
48 楼
frankly speaking I didnt read that article in detail but i dont think that
solution is desired in a normal interview...
【在 H****r 的大作中提到】
: If stable sorting desired then it's getting complicated. There's some
: article on this:
: "Stable minimum space partitioning in linear time"
: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.25.555
solution is desired in a normal interview...
【在 H****r 的大作中提到】
: If stable sorting desired then it's getting complicated. There's some
: article on this:
: "Stable minimum space partitioning in linear time"
: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.25.555
t*e
49 楼
Yes. This paper is indeed talking about the same problem. It is too hard for
an interview.
an interview.
s*n
50 楼
每个元素最多swap两次就能到位，所以是O(n)的
【在 z*****n 的大作中提到】
: 好办法，不错！
: 不过，这种方法，平均情况好像是O(n^2)的，可能第三部要swap n次才能swap到合适位
: 置；
: 另外，对关键词0，1，2这种情况行，因为可以恢复；
: 如果是关键字是正数、0、负数，按照 >0, =0, <0 进行分，感觉就不行了，最后没法
: 恢复。
【在 z*****n 的大作中提到】
: 好办法，不错！
: 不过，这种方法，平均情况好像是O(n^2)的，可能第三部要swap n次才能swap到合适位
: 置；
: 另外，对关键词0，1，2这种情况行，因为可以恢复；
: 如果是关键字是正数、0、负数，按照 >0, =0, <0 进行分，感觉就不行了，最后没法
: 恢复。
H*r
51 楼
// the following requires key is of type int or unsigned int
a[i].key = aidx++;
// which might not be true. The key might be only 2 bits for "00", "01", and
"10"
【在 s******n 的大作中提到】
: Data a[size];
: ...
: int l=0,m=0;
: for (int i=0; i
: else if (a[i].key==1) m++;
: else n++;
: }
: int aidx = 0;
: int bidx = 0;
a[i].key = aidx++;
// which might not be true. The key might be only 2 bits for "00", "01", and
"10"
【在 s******n 的大作中提到】
: Data a[size];
: ...
: int l=0,m=0;
: for (int i=0; i
: else if (a[i].key==1) m++;
: else n++;
: }
: int aidx = 0;
: int bidx = 0;
k*r
52 楼
但既然已经有2个公司把这个题目当作电面了，难道存在一个cheap answer?
我大致看了一下Hector贴的那篇论文，满足要求的应该是简化后的algorithm D.
但论文没详细描述，只说
a simple algorithm exists which is based on the wheel technique [Programming Pearls， Section 10.2].)
哪位有这本书的说说这个wheel technique是个什么东西？
for
【在 t********e 的大作中提到】
: Yes. This paper is indeed talking about the same problem. It is too hard for
: an interview.
我大致看了一下Hector贴的那篇论文，满足要求的应该是简化后的algorithm D.
但论文没详细描述，只说
a simple algorithm exists which is based on the wheel technique [Programming Pearls， Section 10.2].)
哪位有这本书的说说这个wheel technique是个什么东西？
for
【在 t********e 的大作中提到】
: Yes. This paper is indeed talking about the same problem. It is too hard for
: an interview.
d*u
53 楼
Dutch national flag中间的也会乱
【在 s******n 的大作中提到】
: Dutch national flag只能保证middle的不打乱，up和low部分全搞乱
【在 s******n 的大作中提到】
: Dutch national flag只能保证middle的不打乱，up和low部分全搞乱
A*u
54 楼
这个题目大家怎么讨论的这么火热
用counting sort 思路可以吗？
开一个int[3] 算是O(1)吧.
然后像counting sort,
从后往前恢复序列， 不就是O(N), O(1)算法
【在 s******n 的大作中提到】
: Dutch national flag只能保证middle的不打乱，up和low部分全搞乱
用counting sort 思路可以吗？
开一个int[3] 算是O(1)吧.
然后像counting sort,
从后往前恢复序列， 不就是O(N), O(1)算法
【在 s******n 的大作中提到】
: Dutch national flag只能保证middle的不打乱，up和low部分全搞乱
a*y
55 楼
俺写了一个, 没有测试过只有1, 2, 或者0 的情况...
请高手指正...
思路就是维护了三个指针p0, p1, p2, 分别指向了数组index最小的0, 1, 2值所在位置,
然后遍历的过程中,不断swap(值和指针同时swap), 复杂度为O(n), 常数空间.
请高手们多指正了!
#include
#include
using namespace std;
class MITbbSolver
{
public:
MITbbSolver() {}
virtual ~MITbbSolver() {}
public:
void swap_pv(int* &p1, int* &p2) {
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
int* p = p1;
p1 = p2;
p2 = p;
return;
}
void sort_012_array(int* a, int n)
{
if (NULL==a || n<1) return;
int *p1, *p2, *p0;
p0 = p1 = p2 = NULL;
int i;
int* p = NULL, *pcur = NULL;
for (i = 0; i < n; i++) {
if (a[i]==0 && NULL==p0) {
p0 = a + i;
break;
}
}
if (p0 != a) {
pcur = a;
swap_pv(p0, pcur);
}
for (pcur = p0; pcur < a + n; pcur++) {
if (*pcur==1 && NULL==p1) {
p1 = pcur;
}
if (*pcur==2 && NULL==p2) {
p2 = pcur;
}
}
if (p1==NULL && p2==NULL) {
return;
}
if (p1 > p2) {
swap_pv(p1, p2);
}
for (pcur = p1; pcur < a + n; pcur++) {
if (*pcur==2) {
p2 = pcur;
break;
}
}
for (i = 0; i < n; i++) {
p = a + i;
if (*p==0 && p>p1) {
pcur = p;
if (pcur > p1) {
swap_pv(pcur, p1);
p1 = pcur + 1;
}
if (p1 > p2) {
swap_pv(p1, p2);
p2 = p1 + 1;
}
}
if (*p==1 && p>p2) {
pcur = p;
if (pcur > p2) {
swap_pv(pcur, p2);
p2 = pcur + 1;
}
}
} //for//
return;
}
void test_sort_012_array()
{
int a[] = {0, 2, 2, 2, 1, 1, 1, 0, 1, 2, 0, 0, 2, 2, 1, 1};
int n = sizeof(a) / sizeof(a[0]);
// original
copy(a, a+n, ostream_iterator(cout, " "));
cout << endl;
sort_012_array(a, n);
// sorted result
copy(a, a+n, ostream_iterator(cout, " "));
cout << endl;
return;
}
};
请高手指正...
思路就是维护了三个指针p0, p1, p2, 分别指向了数组index最小的0, 1, 2值所在位置,
然后遍历的过程中,不断swap(值和指针同时swap), 复杂度为O(n), 常数空间.
请高手们多指正了!
#include
#include
using namespace std;
class MITbbSolver
{
public:
MITbbSolver() {}
virtual ~MITbbSolver() {}
public:
void swap_pv(int* &p1, int* &p2) {
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
int* p = p1;
p1 = p2;
p2 = p;
return;
}
void sort_012_array(int* a, int n)
{
if (NULL==a || n<1) return;
int *p1, *p2, *p0;
p0 = p1 = p2 = NULL;
int i;
int* p = NULL, *pcur = NULL;
for (i = 0; i < n; i++) {
if (a[i]==0 && NULL==p0) {
p0 = a + i;
break;
}
}
if (p0 != a) {
pcur = a;
swap_pv(p0, pcur);
}
for (pcur = p0; pcur < a + n; pcur++) {
if (*pcur==1 && NULL==p1) {
p1 = pcur;
}
if (*pcur==2 && NULL==p2) {
p2 = pcur;
}
}
if (p1==NULL && p2==NULL) {
return;
}
if (p1 > p2) {
swap_pv(p1, p2);
}
for (pcur = p1; pcur < a + n; pcur++) {
if (*pcur==2) {
p2 = pcur;
break;
}
}
for (i = 0; i < n; i++) {
p = a + i;
if (*p==0 && p>p1) {
pcur = p;
if (pcur > p1) {
swap_pv(pcur, p1);
p1 = pcur + 1;
}
if (p1 > p2) {
swap_pv(p1, p2);
p2 = p1 + 1;
}
}
if (*p==1 && p>p2) {
pcur = p;
if (pcur > p2) {
swap_pv(pcur, p2);
p2 = pcur + 1;
}
}
} //for//
return;
}
void test_sort_012_array()
{
int a[] = {0, 2, 2, 2, 1, 1, 1, 0, 1, 2, 0, 0, 2, 2, 1, 1};
int n = sizeof(a) / sizeof(a[0]);
// original
copy(a, a+n, ostream_iterator
cout << endl;
sort_012_array(a, n);
// sorted result
copy(a, a+n, ostream_iterator
cout << endl;
return;
}
};
a*y
56 楼
好像不是stable的... = =
等高手解答吧....
等高手解答吧....
a*y
57 楼
swan 兄弟的这个我觉得是完全符合要求的, 不知道还有哪里需要改进的??
求指导...
【在 s******n 的大作中提到】
: 好了，终于想出来了：
: 第一遍：count0，1，2的个数l, m, n
: 第二遍：根据l,m,n很容易确定每个元素最终要挪到哪个位置，把数组元素值改成最终
: 目的地的下标
: 第三遍：根据a[i]!=i的条件进行swap到最终位置
: 第四遍：根据l,m,n恢复数组元素值为0,1,2
求指导...
【在 s******n 的大作中提到】
: 好了，终于想出来了：
: 第一遍：count0，1，2的个数l, m, n
: 第二遍：根据l,m,n很容易确定每个元素最终要挪到哪个位置，把数组元素值改成最终
: 目的地的下标
: 第三遍：根据a[i]!=i的条件进行swap到最终位置
: 第四遍：根据l,m,n恢复数组元素值为0,1,2
X*K
58 楼
我觉得不能假定数组里存的就是数字123，如果是这样的话那直接counting sort就好
了。题目里说了数组存的是一条条记录，而这些记录的关健字是123，所以得假定数组
里放的是记录指针，这样就不能改成数组下标。
【在 a***y 的大作中提到】
: swan 兄弟的这个我觉得是完全符合要求的, 不知道还有哪里需要改进的??
: 求指导...
了。题目里说了数组存的是一条条记录，而这些记录的关健字是123，所以得假定数组
里放的是记录指针，这样就不能改成数组下标。
【在 a***y 的大作中提到】
: swan 兄弟的这个我觉得是完全符合要求的, 不知道还有哪里需要改进的??
: 求指导...
t*e
59 楼
This is a good solution. But I think changing key can be counted as O(N)
space is used. This may be what interviewer want though.
【在 a***y 的大作中提到】
: swan 兄弟的这个我觉得是完全符合要求的, 不知道还有哪里需要改进的??
: 求指导...
s*n
60 楼
稳定吗？假设数组是 2,2,0,...你第一步把0和2对调，打乱了两个2的次序。
【在 a***y 的大作中提到】
: swan 兄弟的这个我觉得是完全符合要求的, 不知道还有哪里需要改进的??
: 求指导...
【在 a***y 的大作中提到】
: swan 兄弟的这个我觉得是完全符合要求的, 不知道还有哪里需要改进的??
: 求指导...
d*u
61 楼
为什么最多swap两次就能到位？
【在 s******n 的大作中提到】
: 每个元素最多swap两次就能到位，所以是O(n)的
【在 s******n 的大作中提到】
: 每个元素最多swap两次就能到位，所以是O(n)的
n*t
62 楼
swap那步总共需要o(n^2)，同不理解为啥每回两次到位
【在 d**u 的大作中提到】
: 为什么最多swap两次就能到位？
【在 d**u 的大作中提到】
: 为什么最多swap两次就能到位？
A*u
63 楼
是O(N)
若A[i] != i;
假设A[i] = k; swap(A[i],A[k]), 那么A[k] = k了.
如果A[i] 还是 A[i] != i, 继续
因此，每次swap,都会使得一个 A[x] == x.
所以O(N)
for(int i = 0; i < N; ++i)
{
while ( A[i] != i ){
int k = A[i];
swap(A[i],A[k]);
}
}
swan的方法真好
【在 n*******t 的大作中提到】
: swap那步总共需要o(n^2)，同不理解为啥每回两次到位
若A[i] != i;
假设A[i] = k; swap(A[i],A[k]), 那么A[k] = k了.
如果A[i] 还是 A[i] != i, 继续
因此，每次swap,都会使得一个 A[x] == x.
所以O(N)
for(int i = 0; i < N; ++i)
{
while ( A[i] != i ){
int k = A[i];
swap(A[i],A[k]);
}
}
swan的方法真好
【在 n*******t 的大作中提到】
: swap那步总共需要o(n^2)，同不理解为啥每回两次到位
h*e
64 楼
i don't think his method is good.. it is a trivial problem if you are
allowed to change the content
allowed to change the content
l*i
65 楼
这个是老题了，有人写了篇paper，好像要用到permutation group。总之interview拿
这个来考别人的就是诚心不让你过的，没啥意思。给solution的同学以后能不能给个大
概思路加上证明思路，单纯给code大多数不明白
这个来考别人的就是诚心不让你过的，没啥意思。给solution的同学以后能不能给个大
概思路加上证明思路，单纯给code大多数不明白
c*x
66 楼
这题挺难的
0,1,2肯定是value，如果直接是数组元素的话就没有必要stable了。
用到swap基本就不stable了。
0,1,2肯定是value，如果直接是数组元素的话就没有必要stable了。
用到swap基本就不stable了。
h*9
67 楼
花了两三分钟自己想了出来，然后看到你这个，google后发现和我想的完全一样，哈哈。
【在 g*********e 的大作中提到】
: the dutch flag problem
: search google
l*t
68 楼
可以这样做
step1 记录数组里面有多少 0,1,2
num_0 = num_of_0;
num_1 = num_of_1;
num_2 = num_of_2;
0 to num0 为zone1 num0 to num0+num1 定义为zone2 num0+num1 to num0+num1+num2
定义为zone3
step2
zone1里面 如果是0 不动 如果是2 和zone3里面的0互换
这样zone1和zone3 里面 一个有0,1,2，一个只有0,1 或者1,2
假设是0,1的情况 也就是zone1只剩下0,1，zone3还有0,1,2
那么扫zone2， 把里面的2 全部和zone3里面的0交换
这样可以保证 zone1只有0,1， zone2有0,1,2， zone3 只有1,2
接下来zone1里面的1和zone2里面的0换
zone3 里面的1和zone2里面的2换
这样 zone1只有0 zone2只有1 zone3只有2
step1 记录数组里面有多少 0,1,2
num_0 = num_of_0;
num_1 = num_of_1;
num_2 = num_of_2;
0 to num0 为zone1 num0 to num0+num1 定义为zone2 num0+num1 to num0+num1+num2
定义为zone3
step2
zone1里面 如果是0 不动 如果是2 和zone3里面的0互换
这样zone1和zone3 里面 一个有0,1,2，一个只有0,1 或者1,2
假设是0,1的情况 也就是zone1只剩下0,1，zone3还有0,1,2
那么扫zone2， 把里面的2 全部和zone3里面的0交换
这样可以保证 zone1只有0,1， zone2有0,1,2， zone3 只有1,2
接下来zone1里面的1和zone2里面的0换
zone3 里面的1和zone2里面的2换
这样 zone1只有0 zone2只有1 zone3只有2
l*t
69 楼
可以这样做
step1 记录数组里面有多少 0,1,2
num_0 = num_of_0;
num_1 = num_of_1;
num_2 = num_of_2;
0 to num0 为zone1 num0 to num0+num1 定义为zone2 num0+num1 to num0+num1+num2
定义为zone3
step2
zone1里面 如果是0 不动 如果是2 和zone3里面的0互换
这样zone1和zone3 里面 一个有0,1,2，一个只有0,1 或者1,2
假设是0,1的情况 也就是zone1只剩下0,1，zone3还有0,1,2
那么扫zone2， 把里面的2 全部和zone3里面的0交换
这样可以保证 zone1只有0,1， zone2有0,1,2， zone3 只有1,2
接下来zone1里面的1和zone2里面的0换
zone3 里面的1和zone2里面的2换
这样 zone1只有0 zone2只有1 zone3只有2
step1 记录数组里面有多少 0,1,2
num_0 = num_of_0;
num_1 = num_of_1;
num_2 = num_of_2;
0 to num0 为zone1 num0 to num0+num1 定义为zone2 num0+num1 to num0+num1+num2
定义为zone3
step2
zone1里面 如果是0 不动 如果是2 和zone3里面的0互换
这样zone1和zone3 里面 一个有0,1,2，一个只有0,1 或者1,2
假设是0,1的情况 也就是zone1只剩下0,1，zone3还有0,1,2
那么扫zone2， 把里面的2 全部和zone3里面的0交换
这样可以保证 zone1只有0,1， zone2有0,1,2， zone3 只有1,2
接下来zone1里面的1和zone2里面的0换
zone3 里面的1和zone2里面的2换
这样 zone1只有0 zone2只有1 zone3只有2
g*y
70 楼
这个方法有问题。zone1 0的位置不一定是排序以后的问题。
step2
zone1里面 如果是0 不动
num2
【在 l********t 的大作中提到】
: 可以这样做
: step1 记录数组里面有多少 0,1,2
: num_0 = num_of_0;
: num_1 = num_of_1;
: num_2 = num_of_2;
: 0 to num0 为zone1 num0 to num0+num1 定义为zone2 num0+num1 to num0+num1+num2
: 定义为zone3
: step2
: zone1里面 如果是0 不动 如果是2 和zone3里面的0互换
: 这样zone1和zone3 里面 一个有0,1,2，一个只有0,1 或者1,2
step2
zone1里面 如果是0 不动
num2
【在 l********t 的大作中提到】
: 可以这样做
: step1 记录数组里面有多少 0,1,2
: num_0 = num_of_0;
: num_1 = num_of_1;
: num_2 = num_of_2;
: 0 to num0 为zone1 num0 to num0+num1 定义为zone2 num0+num1 to num0+num1+num2
: 定义为zone3
: step2
: zone1里面 如果是0 不动 如果是2 和zone3里面的0互换
: 这样zone1和zone3 里面 一个有0,1,2，一个只有0,1 或者1,2
R*1
71 楼
不是 color sort吗？排序0,1,2序列？
某大牛前几天刚贴出来很elegant的code
--不好意思，没看到stable的要求……
某大牛前几天刚贴出来很elegant的code
--不好意思，没看到stable的要求……
相关阅读
一个月老板就给我找了10几个reviewpp第7天了想试试EB1A, 求建议, 谢谢!485 pending期间怎么出国这种情况如何证明sustained claim?怎样准备引用文章，引用我文章的都需要打印出来吗？求ISI作油灯图的方法。办个工作绿卡总共要cost公司多少钱啊请问这样写可以算是独立推荐人吗？I140-审稿证明用把所有的invitation letter 和 thank you letter 附上吗？求助485用的 银行证明有关审稿一问New average citation 连接和一问家庭医生那里先拍得胸片可以吗？Weak EB1B PP 后 第六天 Approved申EB1b, grant能作为award用吗？EAD/AP批了,485是不是快了?EB1b 填表，part 9, Person who preparing the form,请教独立推荐信，同学们快过来！关于通过学校办eb1b