谜题：在一次遍历中将一个由0和1组成的数组排序。

Question

是否可以在一次遍历中，不使用辅助数组的情况下将由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;
    }
}

- prgmrDev

---

你需要什么样的优化？是对数据进行一次遍历吗？ - EvilTeach

是的，解决方案应该在一次解析中实现。 - prgmrDev

解析和传递是不同的东西，即使它们发音相同（对于某些人来说可能是同音异义词）。你的代码表示一个解析。 - Andrew Morton

Answer 1

for (size_t i = 0, count = 0; i < n; i++) {
  if (a[i] == 1) a[count++] = 1;
  if (i >= count) a[i] = 0;
}

- nullptr

---

如果a [0]最初为1怎么办？ - Jiminion

糟糕。谢谢，吉姆，我会修复这个问题的。 - nullptr

@Inspired 我认为 a[count+=a[i]] |= a[i] 可以省去第一个 if 语句。如果我们将循环分成两个部分，第一个循环遍历直到遇到0的1，第二个循环从那里开始，则第二个 if 也可以省略。 - unxnut

@unxnut 那么代码将是无分支的，太棒了。我认为count的初始值应该是-1，因为a[count+=a[i]]会过早地增加count。 - nullptr

我喜欢这个。对我来说，它非常不明显，但是它是正确的 :-) - domen

Answer 2

让我试一下：

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，则交换它们的值，然后继续移动。注意：以下代码未经测试，但大致思路应该是正确的。

- abelenky

---

谢谢，我已经编译了。它运行得很好。由于我在参数n中发送了大小，我们需要修改代码 int* q = &a[n] 为 int* q = &a[n-1]。 - prgmrDev

如果数组全部由1组成，那么while (*p == 1 && p <= q)会越界。应该改为while (p <= q && *p == 1)。 - nullptr

它们确实有意义，但格式化为注释时就没有意义了。我会将我的代码粘贴在答案中，然后删除它 - 你可以看到那个。 - Jonathan Leffler

@JonathanLeffler；你应该制作并附上代码的截图链接（对于<10k用户）:( - haccks

@haccks：这张截图太大了，不适合作为好的截图。而且它只是对一个答案的评论（虽然是一个很长的评论），这就是为什么它被删除了，因为它不是一个答案。努力达到10k，你也可以看到它。:D - Jonathan Leffler

Answer 3

递归怎么样？像往常一样简单而优雅。

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;
}

- user529758

---

有点复杂，我通常避免使用递归解决方案。不管怎样，感谢您的帮助 :) - prgmrDev

优雅，是的，但简单吗？:) 不错的解决方案。 - nullptr

@Inspired 谢谢！这取决于你的口味 :) 我觉得它相当直观。也许我只是太忙于实现我的虚拟机，总是从堆栈的角度思考 :P - user529758

@H2CO3 对于二叉树而言，可以这样实现：queue.push(root); while (!queue.empty()) { node = queue.front(); queue.pop(); if (node!=NULL) { process_node(node); queue.push(node->left); queue.push(node->right); } } :) - nullptr

@Inspired 是的，就是这样！ - user529758

Answer 4

请试一下！

(阅读评论):

#include<stdio.h>
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)。

- Grijesh Chauhan

---

我觉得对于 1,0,0,1,1,0,1 它会失败，让我检查一下。 - Grijesh Chauhan

这将在1,1,1,...,1（在while循环中超出数组边界）失败。 - nullptr

即使是两遍扫描（2-pass），所有方案的时间复杂度都为O(n)，因为O(n)=O(2*n)。 - nullptr

@Inspired 是的，它只需要 n 次迭代，甚至不到 2n...稍微好一点...不是吗？ - Grijesh Chauhan

@GrijeshChauhan 更好了，但它仍然是O(n)或O(2n)或O(1000n)。我只是强调大O符号的含义。 - nullptr

Answer 5

#include<iostream>

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;

- abnvanand

Answer 6

这只是另一种方式。

有两个枢轴，一个从开头，另一个从结尾，就像下面这个：

for(int i=0, j=n-1;i<j;)
{
if(a[i]==1 && a[j]==0) swap(a[i],a[j]);
else if(a[i]==1 && a[j]==1) j--;
else if(a[i]==0 && a[j]==0) i++;
else if(a[i]==0 && a[j]==1) {j--; i++;}
}

- MissingNumber