c – 拼图：在一个解析中排序0和1的数组.

发布时间：2020-12-16 03:43:39 所属栏目：百科来源：网络整理

导读：是否可以在一个解析之内按降序排列只有1和0的数组,而不使用辅助数组？例如：假设你有一个数组a [] = {1,1,1},为此预期的输出将是一个[] = {1,0}. 我写了下面的C代码,但是它在2个解析中找到了解.可以优化吗？ void arrange(int a[],int n) { int i,count=0;

是否可以在一个解析之内按降序排列只有1和0的数组,而不使用辅助数组？
例如：假设你有一个数组a [] = {1,1,1},为此预期的输出将是一个[] = {1,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,在右侧找到一个,交换值,然后继续.

(代码未经测试,但轮廓看起来很实在)

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!