d********w
发帖数: 363 | 1 简单型：sort 0， 1数组， O(n)时间，可以使用头尾两个pointer，
i = 0;
j = n-1;
while( i < j){
while( array[i] == 0 && i < j )
i++;
while( array[j] == 1 && j > i )
j--;
if ( i < j )
swap( a[i], a[j] );
}
如果是排序0，1，2数组，就是dutch flag问题， http://en.wikipedia.org/wiki/Dutch_national_flag_problem，跟quicksort中的partition类似
void threeWayPartition(int data[], int size, int low, int high) {
int p = -1;
int q = size;
for (int i = 0; i < q;) {
if (data[i] < low) {
swap(data[i], data[++p]);
++i;
} else if (data[i] >= high) {
swap(data[i], data[--q]);
} else {
++i;
}
}
}
扩展问题
1）如果是n个数字呢，基数排序
2）如果要保证in order呢？
3）让0，1相间排列，如果多余0或1就放在尾部，保证O(n)时间，不使用辅助空间，
i.e.
input: 0 1 1 1 0 0 1 1 1 0
output: 0 1 0 1 0 1 0 1 1 1 | d********w
发帖数: 363 | 2 扩展3，找到一个这么写的，http://pastebin.com/f41fe39d1
大家看看对不
【在 d********w 的大作中提到】
: 简单型：sort 0， 1数组， O(n)时间，可以使用头尾两个pointer，
: i = 0;
: j = n-1;
: while( i < j){
: while( array[i] == 0 && i < j )
: i++;
: while( array[j] == 1 && j > i )
: j--;
: if ( i < j )
: swap( a[i], a[j] );
| d********w
发帖数: 363 | 3 扩展3如果能计数的话，就简单了，只要把1的个数，0的个数统计出来，就知道最后留
几个，前面就直接按01打印了，如果限定不能计数呢
还想到一个问题，如果是求最少的交换次数，例如三色问题，不一定要求0放在最前，
只是相同数字聚在一起。01间隔打印的话，不一定0101，1010也行。该怎么思考呢
【在 d********w 的大作中提到】
: 扩展3，找到一个这么写的，http://pastebin.com/f41fe39d1
: 大家看看对不
| i**********e
发帖数: 1145 | 4 这道题 FB 面试有人贴过，而且听说代码写起来很麻烦.
在网上尝试找关于 Dutch National Flag Problem (DNFP) 的扩展至 k 种颜色的解法
，找了老半天都没找着（连四种颜色的也没找到），代码只好自己写了.
今天写 DNFP 四种颜色排序基本写对了，但是某些 test cases 不能通过。主要难度在
于当此颜色为第一颜色的时候应该怎么交换。研究了老半天，终于开窍了。原来是忘掉
了一个很重要不变量（invariant），就是 0 <= r <= w <= b < n （这里指的是原题
的三种颜色，r=red, g=green, b=blue，扩展至 k 种颜色的不变量为 0 <= mid[0] <=
mid[1] <= ... <= mid[k-1] < n）.
DNFP 四种颜色写对了之后，思路就清晰了，非常容易扩展至 k 种颜色。利用一个内循
环，来保持不变量 0 <= mid[0] <= mid[1] <= ... <= mid[k-1] < n. 这内循环似乎
很耗时，但少了这内循环，我又不知道怎样才能保持以上的不变量，望高手指教.
顺便介绍一个写得很好关于 DNFP 的文章，受益匪浅.
http://www.iis.sinica.edu.tw/~scm/ncs/2010/10/dutch-national-fl
还有另外一段文章，有模拟 DNFP 的运行，写得也不错。但是不完全对，其文章根本就没提到很重要的不变量，也就是 0 <= r <= w <= b < n.
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/
以下是我写的代码，欢迎大家讨论.
// Dutch National Flag Problem (DNFP) generalized to k different
colors.
// k = {0, 1, 2, ..., k-1}
// pre-condition: n >= 0, k >= 2
void SortK(int A[], int n, int k) {
assert(n >= 0 && k >= 2);
int *mid = new int[k];
// init values to satisfy invariant below
for (int i = 0; i < k-1; i++)
mid[i] = 0;
mid[k-1] = n-1;
// invariant:
// 0 <= mid[0] <= mid[1] <= mid[2] <= ... <= mid[k-1] < n,
// A[0..mid[0]-1] = 0,
// A[mid[0]..mid[1]-1] = 1,
// A[mid[1]..mid[2]-1] = 2,
// ...
// A[mid[k-2]..mid[k-1]] = mixed colors,
// A[mid[k-1]+1..n-1] = k-1.
// the range of mixed colors is: [ mid[k-2] ... mid[k-1] ]
// the array is sorted when mid[k-2] > mid[k-1] (ie, no more mixed colors)
while (mid[k-2] <= mid[k-1]) {
if (A[mid[k-2]] == k-1) {
swap(A[mid[k-2]], A[mid[k-1]]);
mid[k-1]--;
} else if (A[mid[k-2]] == k-2) {
mid[k-2]++; // no swap needed, advance
} else {
int x = A[mid[k-2]];
swap(A[mid[k-2]], A[mid[x]]);
mid[x]++;
// for maintaining invariant: (mid[x+1], mid[x+2] ... mid[k-2]) >= mid[x]
for (int i = x+1; i <= k-2; i++)
if (mid[i] < mid[x])
mid[i] = mid[x];
}
}
delete[] mid;
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com | j********x
发帖数: 2330 | 5 2, O(n) space radix sort is stable
3, "no extra memory" is ill-defined, is index considered "extra"? | g*********s
发帖数: 1782 | 6 i think O(1) space is fine.
【在 j********x 的大作中提到】
: 2, O(n) space radix sort is stable
: 3, "no extra memory" is ill-defined, is index considered "extra"?
|
|
