困惑：在一个解析类的0和1的阵列。 [英] Puzzle: Sort an array of 0's and 1's in one parse.

问题描述

是否有可能仅由1和0阵列安排在不使用辅助阵列中的一个解析内降序排列？结果
例如：假设你有一个数组 A [] = {1,0,0,0,1,0,1} ，这个预期产量将 A [] = {1,1,1,0,0,0,0} 。

我已经写了下面的C code，但它发现在2解析解。难道是优化？

 无效安排（int类型的[]，INT N）{
    INT I，计数= 0;
    对于（i = 0; I＆LT; N;我++）{
            如果（一个由[i] == 1）
                    算上++;
            一个由[i] = 0;
    }
    对于（i = 0; I＆LT;计数;我++）{
            一个由[i] = 1;
    }
}
 

解决方案

让我试试这个：

 无效安排（int类型的[]，INT N）
{
    INT * P = A;
    为int * Q =＆放大器;一个[N-1];    而（P＆下; = Q）
    {
        而（* P == 1和;＆放大器; P＆下; = q）的/ *找到一个零，从前方开始* /
        {
            ++磷;
        }
        而（* Q ​​== 0安培;＆安培; P＆LT; = Q）/ *查找一，从后面开始* /
        {
            --q;
        }        如果（P＆所述; Q）/ * * P ==零，和* Q ==其中，p是为q的左侧。 * /
        {
            * p值= 1;
            * Q = 0;
        }
    }
}
 

这适用于两个指针，一个从前面看，其他开始在后面，他们都向中间移动，直到他们满足。

一路上，如果这两个指针找到在左侧0，右侧一个1，交换值，则继续

的（code未经测试，但轮廓似乎固体）的

Is it possible to arrange the array made up of only 1's and 0's in descending order within one parse without using auxiliary array?
For example: Suppose you have an array a[]={1,0,0,0,1,0,1}, for this the expected output will be a[]={1,1,1,0,0,0,0}.

I have written the below C code but it finds the solution in 2 parses. Could it be optimized?

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

解决方案

Let me try this:

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

This works with two pointers, one starting at the front, the other starting at the back, and they both move towards the middle until they meet.

Along the way, if the two pointers find a 0 on the left and a 1 on the right, swap the values, then continue.

(code is untested, but the outline seems solid)

这篇关于困惑：在一个解析类的0和1的阵列。的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！