如何在不改变相对位置的情况下将整数数组排序为负、零、正部分？

发布于 2024-10-23 20:27:12 字数 696 浏览 1 评论 0原文

给出一个 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++]);  
    }  
}

原文

Give an O(n) algorithm which takes as input an array S, then divides S into three sets: negatives, zeros, and positives. Show how to implement this in place, that is, without allocating new memory. And you have to keep the number's relative sequence.
for example:
{-1, 4, 0, -2, 1, 2} ==> {-1, -2, 0, 4, 1, 2}

I am not sure whether or not such an solution exits. The best solutions I can think out are:

Solution 1: Using an extra integer array, then traverse the whole array to get negatives, then 0s, then positives.

Solution 2: Do not keep number's relative sequence. Then loop the array two times:

    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++]);  
    }  
}

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

送舟行 2024-10-30 20:27:12

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

回复收藏 0 原文

却一份温柔 2024-10-30 20:27:12

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

回复收藏 0 原文

心凉 2024-10-30 20:27:12

零是难以区分的，所以我想你并不关心它们是否会被交换，甚至只是在最后被覆盖（即，在我们完成将正数和负数移动到数组的两端之后，我们只是将中间部分清零）。

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

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

当然，针对您的问题的算法可以实现稳定的二进制分区（只是一个没有零的数组）。相反，如果数组有零，您仍然可以使用二进制分区来完成脏工作：直接扫描数组，将遇到的每个零与下一个负值交换（跟踪它在哪里，这样您就不会这样做） n^2 整体扫描），结果是

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

然后进行两个二进制分区以获得

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

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

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

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

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

如果零与其他类型一样多，则在执行 1 然后 2 然后再次 1 后完成此操作。

回复收藏 0 原文

烟燃烟灭 2024-10-30 20:27:12

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

编辑：
不，那是 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) 算法。不幸的是，stable_partition 函数来自 c++ stl 的比较只有 O(n) 次，但如果没有额外的空间可用，则需要 O(n log n) 次交换。

不过这篇文章："稳定线性时间内的最小空间划分” 似乎表明它在 O(n) 内是可能的。我想我对它的理解还不够清楚，无法在这里清楚地总结它。

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

Can't this be done simply using any "stable sort" performed with a custom comparitor which only checks the sign?

Edit:
No, that's O(n log n).

One thing you can do in linear time is reduce the problem. Since the zeros can't be ordered (how do you tell one from the other?), you can make a pass where you walk through the array, skipping the zeroes and filling in with the non-zero values. Then add the correct number of zeros at the end.

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

Now you can ignore the last section and the problem becomes finding an O(n) algorithm for a stable partition around 0. Unfortunately, the stable_partition function from the c++ stl has only O(n) comparisons, but O(n log n) swaps if no additional space is available.

However, this article: "Stable minimum space partitioning in linear time" seems to indicate that it is possible in O(n). I don't think I understand it well enough to summarize it clearly here.

If that works, The final step is to insert the zeros back inbetween the partitions, which is also O(n), since the zeros have no order to maintain.

回复收藏 0 原文