13

给出一个 O(n) 算法，该算法将数组 S 作为输入，然后将 S 分为三组：负数、零数和正数。展示如何就地实现这一点，即不分配新内存。而且你必须保持数字的相对顺序。例如：{-1, 4, 0, -2, 1, 2} ==> {-1, -2, 0, 4, 1, 2}

我不确定这样的解决方案是否存在。我能想到的最佳解决方案是：

解决方案1：使用一个额外的整数数组，然后遍历整个数组得到负数，然后是0，然后是正数。

解决方案2：不要保持数字的相对顺序。然后循环数组两次：

    template <typename Type>  
void Partion(Type *array, int begin, int end, Type v, int &l, int &r) 
{  
    l = begin;  
    for (int i=begin; i!=end; ++i)  
    {  
        if (array[i] < v)  
            swap(array[i], array[l++]);  
    }  
    r = l;  
    for (int j=l; j!=end; ++j)  
    {  
        if (array[j] == v)  
            swap(array[j], array[r++]);  
    }  
}
4

5 回答 5

15

这是Edsger Dijkstra 研究的荷兰国旗问题的一个例子。有趣的是，在 O(n) 时间和 O(1) 空间中运行该问题的稳定解决方案是已知的（或者至少，在我上次查阅文献时，不存在该问题的已知解决方案）。

于 2011-03-18T05:17:54.757 回答
3

我不确定这是否有帮助，但是将稳定划分为三个类的要求可以简化为稳定划分为两个类的问题：将负数与非负数分开，然后将正数与非正数分开。如果二分类问题可以在 O(1) 空间和 O(n) 时间内解决，则可以应用两次解决方案来解决原始问题。

于 2011-03-18T07:55:52.800 回答
1

零是无法区分的，所以我认为您不在乎它们是否被交换或什至只是在最后被覆盖（即，在我们完成将正数和负数移动到数组的两端之后，我们只是将中间部分归零）。

如果您正在查看整数只是更大事物的键的情况，那么情况可能并非如此 - 您可能希望保留零并稳定分区。但如果没有，这里有两个见解：

首先，您的问题与稳定的二进制分区问题相同。

解决您问题的算法当然会进行稳定的二进制分区（只是一个没有零的数组）。相反，如果数组有零，您仍然可以使用二进制分区来做脏工作：直接扫描数组，将遇到的每个零交换为下一个负值（跟踪它的位置，这样您就不会这样做n^2 整体扫描），导致

[混合 -,+][可能额外的零][混合 0,+]。

然后你做两个二进制分区得到

[-][+][0][+]

并移动 + 值以获得所需的结果。

带有二进制分区的 AFAIK，您可以选择稳定、就地和 O(n) 中的任意两个。所以看起来你运气不好，但显然就地 O(n*log n) 算法被称为使用 log(n) 暂存空间的 O(n) 算法。

其次，如果可以保证零的数量至少为 f(n)，零可以弥补暂存空间的不足；在 O(n^2/f(n)) 时间内获得稳定的就地分区很简单。特别是，如果零至少是数组的某个常数部分，则只需运行这两个步骤即可获得 O(n) 运行时间，直到完成：

  1. 直接扫描数组，将遇到的每个零与下一个负值交换
  2. 向左扫描数组，将遇到的每个零与下一个正值交换

如果零与其他类型中的任何一种一样多，则在执行 1 然后 2 再执行 1 之后完成。

于 2011-08-31T06:42:00.447 回答
0

这不能简单地使用使用仅检查符号的自定义比较器执行的任何“稳定排序”来完成吗？

编辑：
不，那是 O(n log n)。

您可以在线性时间内做的一件事是减少问题。由于无法对零进行排序（如何区分一个与另一个？），您可以在遍历数组的位置进行传递，跳过零并填充非零值。然后在末尾添加正确数量的零。

j=0;
for (i=0;i<N;i++) {
  if (A[i]) {
     A[j++]=A[i];
  }
}
while (j<N) {
   A[j++]=0;
}

现在您可以忽略最后一部分，问题变成为 0 附近的稳定分区找到 O(n) 算法。不幸的是，来自 c++ stlstable_partition的函数只有 O(n) 比较，但 O(n log n) 交换如果没有额外的空间可用。

然而，这篇文章：“Stable minimum space partitioning in linear time”似乎表明它在 O(n) 中是可能的。我认为我理解得不够好，无法在这里清楚地总结一下。

如果可行，最后一步是将零重新插入分区之间，这也是 O(n)，因为零没有要维护的顺序。

于 2011-03-18T03:24:39.687 回答
0

C++ 库有一个stable_partition算法，当它就地运行时需要n次比较和 O( n log n ) 交换。

正如@Ted指出的那样，这个问题需要对该算法进行两次应用。

于 2011-03-18T11:38:29.500 回答