拼图：在一个解析中对0和1的数组进行排序。
是否可以在一个解析中按顺序排列仅由1和0组成的数组而不使用辅助数组？
例如：假设你有一个数组a[]={1,0,0,0,1,0,1} ，为此预期的输出将是a[]={1,1,1,0,0,0,0} 。
我编写了下面的C代码，但它在2个解析中找到了解决方案。 可以优化吗？
void arrange(int a[],int n) { int i,count=0; for(i=0;i<n;i++) { if(a[i]==1) count++; a[i]=0; } for(i=0;i<count;i++) { a[i]=1; } }
让我试试这个：
void arrange(int a[],int n) { int* p = a; int* q = &a[n-1]; while (p <= q) { while (*p == 1 && p <= q) /* Find a Zero, starting from the front */ { ++p; } while (*q == 0 && p <= q) /* Find a One, starting from the back */ { --q; } if (p < q) /* *p == Zero, and *q == One, and p is to the left of q. */ { *p = 1; *q = 0; } } }
这有两个指针，一个从前面开始，另一个从后面开始，它们都向中间移动直到它们相遇。
一路上，如果两个指针在左边找到0而在右边找到1，则交换值，然后继续。
（代码未经测试，但大纲看起来很稳固）
for (size_t i = 0, count = 0; i < n; i++) { if (a[i] == 1) a[count++] = 1; if (i >= count) a[i] = 0; }
递归怎么样？ 一如既往的简洁优雅。
void countAndRewrite(int arr[], size_t n, size_t *cone, size_t total) { if (n) { if (arr[0]) ++*cone; countAndRewrite(arr + 1, n - 1, cone, total); arr[0] = total - n < *cone; } } int main() { int arr[] = { 0, 1, 0, 1, 1, 1, 0 }; size_t cone = 0; countAndRewrite(arr, 7, &cone, 7); for (size_t i = 0; i < 7; i++) printf("arr[%zu] = %d\n", i, arr[i]); return 0; }
试试看！
（阅读评论）：
#include int main(void){ int a[]={1,0,0,0,1,0,1}; int n = 7, i, index = 0; while(index < n && a[index]) index++; // skip initial 1's for(i = index; i < n; i++){ if(a[i]) a[index++] = 1; // if `1` at a[i] make its 0 and a[i] = 0; // make at index 1. } for(i = 0; i < n; i++){ printf("%3d", a[i]); } return 1; }
检查工作代码@ ideone的链接：
案例1： {1,0,0,0,1,0,1}
案例2： {1,0,1,1,1,0,0,1,0,1, 1}
案例3： {1,1,1,1,1,1,1}
案例4： {0, 0, 0, 0, 0, 0, 0}
案例5： {0, 0, 0, 1, 1, 1, 1}
所以我认为它的工作正确！
它很简单，只需要n次迭代。
复杂性明智的O(n) 。
只是另一种方式。
从下面开始有一个两个枢轴，另一个像下面一个，
for(int i=0, j=n-1;i
#include using namespace std; int main() { int arr[] = {1, 1, 1, 1, 1, 0, 0, 0}; int N = sizeof(arr) / sizeof(arr[0]); int p = 0, q = 1; while (q != N) { if (arr[p] > arr[q]) { arr[p] = 0; arr[q] = 1; p++; q++; } else { q++; if (arr[p] == 0) p++; } } for (int i = 0; i < N; i++) cout << arr[i]; return 0;