拼图:在一个解析中对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;
    }
}

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

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,则交换值,然后继续.

(代码未经测试,但大纲看起来很稳固)