9

是否可以在不使用辅助数组的情况下在一次解析中按降序排列仅由 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;
    }
}
4

6 回答 6

6 
for (size_t i = 0, count = 0; i < n; i++) {
  if (a[i] == 1) a[count++] = 1;
  if (i >= count) a[i] = 0;
}
于 2013-07-27T18:14:05.670 回答
5

让我试试这个：

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

（代码未经测试，但大纲看起来很扎实）

于 2013-07-27T18:16:59.130 回答
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;
}
于 2013-07-27T18:19:57.993 回答
2

试试看！

（阅读评论）：

#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： 案例 2：案例 3：案例 4：案例 5：{1,0,0,0,1,0,1}
{1,0,1,1,1,0,0,1,0,1, 1}
{1,1,1,1,1,1,1}
{0, 0, 0, 0, 0, 0, 0}
{0, 0, 0, 1, 1, 1, 1}

所以我认为它工作正常！
它很简单，它只需要n迭代。
复杂性明智O(n)。

于 2013-07-27T18:29:15.367 回答
0

只是另一种方式。

有两个枢轴，一个从开始，另一个在结束，如下图所示，

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++;}
}
于 2013-10-01T12:18:55.563 回答
0 
#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;

于 2015-10-19T15:11:13.840 回答