3

可能重复：
哪种算法可以只用 O(N) 移动就地进行稳定的二进制分区？

这是我被击中的面试问题之一

问题： 给定一个正负整数数组，您需要将正数移到一侧，将负数移到另一侧，并且顺序不变。前任。{-1,5,3,-8,4,-6,9} 到 {-1,-8,-6,5,3,4,9}。这应该在 O(n) 中完成，并且不需要额外的 array 。

首先我想通过快速排序来做到这一点

伪代码

找到最接近零的元素。使其成为枢轴元素。然后在数组上应用一次快速排序。这是 O(n) 。

唉! 但是快速排序不是稳定排序？

之后我提出了以下解决方案

伪代码：

最初，增加电流直到第一个 +ve 数字和减量结束直到最后一个 -ve 数字

如果 current 为负，则增加 current 如果 current 为正，则将其与 end 的元素交换并减少 current 和 end 如果 current >= end ，则中断。

仍然没有得到正确的答案。需要这方面的建议

4

2 回答 2

0

std::stable_partition 完全符合您的要求。

对于 C++11，执行

std::stable_partition(
  array.begin(), array.end(),
  [] (int i) { return i < 0; });
于 2012-07-05T04:24:27.903 回答
0

如果结果数组与源数组不同，您可以分两遍轻松完成：

p = 0;   //current index in result array

For i = 0 to length - 1 :
    If source[i] < 0 then
        result[p] = source[i]
        increment p
    End if
End for

For i = 0 to length - 1 :
    If source[i] >= 0 then
        result[p] = source[i]
        increment p
    End if
End for

如果你想就地做，那就有点棘手了。您可以尝试冒泡排序，但这是 O(n^2)：

n = 0  // number of negative items found

For i = 0 to length - 1 :
    If array[i] < 0 then
        For j = i - 1 downto n :
            swap array[j+1] and array[j]
        End for

        increment n
    End if
End for

不幸的是，我想不出一个既是 O(n) 又不需要分配额外数组的解决方案。

于 2012-07-05T06:00:37.460 回答