w****o
发帖数: 2260 | 1 荷兰国旗的问题在：
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/
这个问题可以扩展到多于3个颜色的问题。比如扩展到20种颜色，该如何解决？难道需
要20多个变量吗？如果简单的模仿3个颜色的解法，会显得很罗嗦。
谁有好的想法？
好像这个版上有人面试的时候被问到过20种颜色如何排序的问题？能不能谁给讲讲？
谢谢！ |
i**********e
发帖数: 1145 | 2 这个扩展到只对 k 种颜色进行排序非常繁琐，被问到的概率也不大。你要是有兴趣的
话我可以贴出我之前写过的代码。 |
c****p
发帖数: 6474 | 3 可以用一个数组维护各段的起始下标。
找unknown的元素归属时可以用二分法在下标数组中查找。
k色旗元素交换的时间复杂度严格讲应该是O(n*k*logk)，n较大时相当于O(n)
【在 w****o 的大作中提到】
: 荷兰国旗的问题在：
: http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/
: 这个问题可以扩展到多于3个颜色的问题。比如扩展到20种颜色，该如何解决？难道需
: 要20多个变量吗？如果简单的模仿3个颜色的解法，会显得很罗嗦。
: 谁有好的想法？
: 好像这个版上有人面试的时候被问到过20种颜色如何排序的问题？能不能谁给讲讲？
: 谢谢！
|
c****p
发帖数: 6474 | 4 这种代码你都写过，膜拜。
【在 i**********e 的大作中提到】
: 这个扩展到只对 k 种颜色进行排序非常繁琐，被问到的概率也不大。你要是有兴趣的
: 话我可以贴出我之前写过的代码。
|
w****o
发帖数: 2260 | 5 你能贴出来的话，最好了。
谢谢啦！
【在 i**********e 的大作中提到】
: 这个扩展到只对 k 种颜色进行排序非常繁琐，被问到的概率也不大。你要是有兴趣的
: 话我可以贴出我之前写过的代码。
|
i**********e
发帖数: 1145 | 6 看了我很久以前写的，当时应该写得满头大汗，现在自己完全忘了，不过幸好有注释，
应该不难理解。（我当时是先写了排4个颜色的，然后扩展到k）
这个复杂度应该不是最优的，后边有个 for 循环应该可以优化。请大家看看给些意见
怎么优化，多谢指教。
// Dutch National Flag Problem (DNFP) generalized to k different set of
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;
} |
c****p
发帖数: 6474 | 7 void swap(int *a, int i, int j)
{
int tmp;
if(i == j)
return;
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
void flags(int* a, int n, int k)
{
int ind[k];
int i,j;
int low, high;
int tmp, key;
low = k / 2 - 1;
high = low + 1;
//ind = malloc(k * sizeof(int));
for(i = 0; i < k; i++)
{
ind[i] = (i < high)? 0 : n - 1;
}
i = 0;
while(ind[low] != (ind[high] + 1))
{
key = i;
tmp = a[key];
if(tmp <= low)
{
for(j = low; j >= 0; j--)
{
swap(a, key, ind[j]);
if(tmp == j)
{
ind[j]++;
break;
}
else
{
key = ind[j];
ind[j]++;
}
}
i++;
}
else
{
for(j = high; j < n; j++)
{
swap(a, key, ind[j]);
if(tmp == j)
{
ind[j]--;
break;
}
else
{
key = ind[j];
ind[j]--;
}
}
}
}
}
【在 i**********e 的大作中提到】
: 看了我很久以前写的，当时应该写得满头大汗，现在自己完全忘了，不过幸好有注释，
: 应该不难理解。（我当时是先写了排4个颜色的，然后扩展到k）
: 这个复杂度应该不是最优的，后边有个 for 循环应该可以优化。请大家看看给些意见
: 怎么优化，多谢指教。
: // Dutch National Flag Problem (DNFP) generalized to k different set of
: 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);
|
q****x
发帖数: 7404 | 8 count sort不就行了。
【在 w****o 的大作中提到】
: 荷兰国旗的问题在：
: http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/
: 这个问题可以扩展到多于3个颜色的问题。比如扩展到20种颜色，该如何解决？难道需
: 要20多个变量吗？如果简单的模仿3个颜色的解法，会显得很罗嗦。
: 谁有好的想法？
: 好像这个版上有人面试的时候被问到过20种颜色如何排序的问题？能不能谁给讲讲？
: 谢谢！
|
q****x
发帖数: 7404 | 9 count sort不就行了。
【在 w****o 的大作中提到】
: 荷兰国旗的问题在：
: http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/
: 这个问题可以扩展到多于3个颜色的问题。比如扩展到20种颜色，该如何解决？难道需
: 要20多个变量吗？如果简单的模仿3个颜色的解法，会显得很罗嗦。
: 谁有好的想法？
: 好像这个版上有人面试的时候被问到过20种颜色如何排序的问题？能不能谁给讲讲？
: 谢谢！
|
l*****a
发帖数: 14598 | 10 显然不希望你用counting sort
【在 q****x 的大作中提到】
: count sort不就行了。
|
|
|
H***e
发帖数: 476 | 11 counting sort的特例吗？
还有干吗要那么多指针啊， 直接数一遍，记下012的个数，然后往数组里写就可以了。
当然了，这样要走两遍
【在 w****o 的大作中提到】
: 荷兰国旗的问题在：
: http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/
: 这个问题可以扩展到多于3个颜色的问题。比如扩展到20种颜色，该如何解决？难道需
: 要20多个变量吗？如果简单的模仿3个颜色的解法，会显得很罗嗦。
: 谁有好的想法？
: 好像这个版上有人面试的时候被问到过20种颜色如何排序的问题？能不能谁给讲讲？
: 谢谢！
|
c****p
发帖数: 6474 | 12 这样需要额外的非常数空间吧。。。尤其是种类数量上升之后
【在 H***e 的大作中提到】
: counting sort的特例吗？
: 还有干吗要那么多指针啊， 直接数一遍，记下012的个数，然后往数组里写就可以了。
: 当然了，这样要走两遍
|
i**********e
发帖数: 1145 | 13 Good Job，看来你代码没有我写的那么复杂，能说下思路吗？
【在 c****p 的大作中提到】
: void swap(int *a, int i, int j)
: {
: int tmp;
: if(i == j)
: return;
: tmp = a[i];
: a[i] = a[j];
: a[j] = tmp;
: }
: void flags(int* a, int n, int k)
|
q****x
发帖数: 7404 | 14 不需要。不就是计数吗？当然如果有satellite就不行了。
【在 c****p 的大作中提到】
: 这样需要额外的非常数空间吧。。。尤其是种类数量上升之后
|
c****p
发帖数: 6474 | 15 参考了那个参考链接的思路，把数组分成三部分：low, unknown, high
low和high各分k/2种颜色
开一个大小为k的数组ind，ink[i]记录第i种颜色再新来一个元素时应该进入的位置。
比如{0 0 1 2 3 4 4 .......}, ind={2 3 4 5 7.....}
对于每个unknown内的元素，先看属于low还是high；
以low为例，根据ind数组的指示依次交换至该元素所在的部分为止，
并相应地更新ind数组。举个例子：
{0 0 0 1 1 2 2 2 3 3 1 .....}，ind = {3 5 8 10}
第一次交换：{0 0 0 1 1 2 2 2 1 3 3} ind = {3 5 8 11}
第二次交换：{0 0 0 1 1 1 2 2 2 3 3} ind = {3 5 9 11}
第三次：已经换进所在的颜色区，更新ind数组：ind = {3 6 9 11}。
一个元素的交换完成。
【在 i**********e 的大作中提到】
: Good Job，看来你代码没有我写的那么复杂，能说下思路吗？
|
c****p
发帖数: 6474 | 16 这样做速度应该是O(k*n)，
一个test case：
Original array with 28 elements in 17 types:
8 16 3 8 8 13 3 15 15 0 13 16 13 15 3 11 15 5 10 10 0 16 15 11 7 11 10 5
Sorted array with 28 elements in 17 types:
0 0 3 3 3 5 5 7 8 8 8 10 10 10 11 11 11 13 13 13 15 15 15 15 15 16 16 16
【在 c****p 的大作中提到】
: 参考了那个参考链接的思路，把数组分成三部分：low, unknown, high
: low和high各分k/2种颜色
: 开一个大小为k的数组ind，ink[i]记录第i种颜色再新来一个元素时应该进入的位置。
: 比如{0 0 1 2 3 4 4 .......}, ind={2 3 4 5 7.....}
: 对于每个unknown内的元素，先看属于low还是high；
: 以low为例，根据ind数组的指示依次交换至该元素所在的部分为止，
: 并相应地更新ind数组。举个例子：
: {0 0 0 1 1 2 2 2 3 3 1 .....}，ind = {3 5 8 10}
: 第一次交换：{0 0 0 1 1 2 2 2 1 3 3} ind = {3 5 8 11}
: 第二次交换：{0 0 0 1 1 1 2 2 2 3 3} ind = {3 5 9 11}
|
w****o
发帖数: 2260 | 17 我也自己写了一个。其实就是拿到一个值后，根据值得大小，判断应该把者个值放在哪
里，把真正的操作用代码给直接的描述出来。
具体用法：比如有个数组a[]，有4种颜色，数组大小为n,可以调用 DNF_K(a, 4, 0, n-
1)
// this is the code for k colors.
// the element values can be 0, 1, 2, ..., k-1
// partition[i] records the starting index for value i
// partition[0] does not matter, and should be always 0
// partition[k-1] denotes the lower index of unknown section
// h denotes the upper index of unknown section
// sections are :
// 0 1 2 3 ... unknown k-1
// complexity: O(n*k)
//
void DNF_K(int a[], int k, int lowest, int highest)
{
int i;
int h;
int j;
int cur_element;
int *partition;
partition = (int *)malloc(sizeof(int) * k);
for (i = 0; i < k ; i++) {
partition[i] = lowest;
}
h = highest;
while(partition[k-1] <= h)
{
if(a[partition[k-1]] == k - 1){
swap(&a[partition[k-1]], &a[h]);
h--;
} else {
cur_element = a[partition[k-1]];
// swap the first elements in two adjacent sections backward
// from the unknown section until the section for cur_
element+1
for (j = k - 2; j >= cur_element + 1; j--) {
// swap the first elements in two adjacent sections
swap(&a[partition[j]], &a[partition[j+1]]);
//adjust the index for the touched partition
partition[j+1]++;
}
//adjust the index for the section for cur_element + 1
partition[j+1]++;
}
}
free(partition);
}
void swap(int *a, int *b)
{
int c = *a;
*a = *b;
*b = c;
}
【在 i**********e 的大作中提到】
: 这个扩展到只对 k 种颜色进行排序非常繁琐，被问到的概率也不大。你要是有兴趣的
: 话我可以贴出我之前写过的代码。
|
