1

给定以下数组：| 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |

我们必须对上面的数组进行排序，就像右侧的所有 1 和左侧的所有 0 一样。

我在 C++ 中提出了 2 种算法。

第一个：

for(i = 0; i < n; i++) {
    if(a[i] == 1 && i != n - 1) {
        for(j = i + 1; j < n; j++) {
            if(a[j] == 0) {
                temp = a[j];
                a[i] = a[j];
                a[j] = temp;
                break;
            }
        }
    }
}

第二个： 

int x = 0;
for(i = 0; i < n; i++) {
    if(a[i] == 1) {
        for(j = n-x-1; j >= 0; j--) {
            if(a[j] == 0) {
                temp = a[j];
                a[i] = a[j];
                a[j] = temp;
                x++;
                break;
            }
        }
    if(x > n / 2)
    break;
}

你能告诉我两者的时间复杂度吗？哪个表现更好也向我建议了一个更好的算法和解释。谢谢。

4

3 回答 3

15

只需计算个数，然后用零第一个lengthOfArray - sum元素填充数组，然后再填充一个。复杂度为 O(n)。

在这两种情况下，您的复杂度都是 O(n²)

于 2013-10-01T08:38:40.610 回答
3

正如@Alexandru 所说，这很好 O(N) ，你只需要迭代两次

  1. 要找到 0、1 的计数
  2. 用 1、0 填充数组，如 count 所说。

如果您正在寻找另一种替代排序，您可以查看 O(N) 。

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-01T09:09:47.420 回答
2

第一个将在 O(n^2) 时间内对数组进行排序，因为它是冒泡排序的直接含义。但是第二种方法不会对数组进行排序，因为您在从末端横向移动时将 1 与第一个 0 交换。所以如果你的数组是这样的，0 0 0 1 1 1那么第二个代码会将第三个索引中的 1 与第二个索引的 0 交换，最后它看起来像0 0 1 1 1 0. 我不知道那个 x 是什么？

于 2013-10-01T08:45:40.260 回答