logo标签列表

在严格O(n)时间内对整型数组进行排序

c#arrays
8

最近我在面试中被问到了这个问题。

给定一个包含负数和正数的已排序整数数组，如何根据元素的绝对值重新排列数组？

必须在O(n)时间内完成。

输入

{-9,-7,-3,1,6,8,14}

输出

{1,-3,6,-7,8,-9,14}

除了O(n)时间，还有哪些可能的解决方案？

2
找到中点（即最靠近零点的位置），然后从那里向两个方向合并数组 - 这将简化为合并两个已排序的子数组，其保证时间复杂度为O(n)。 - Thomas Jungblut
@ThomasJungblut，您能否进一步解释一下。 - Mudassir Hasan
很简单，你取数组的中间值（在我们的例子中是1），这必须是新数组中的第一个数字（因为我们保证输入的数组是排序好的）。然后，你合并两个半部分（上半部分和下半部分）： 中间值=1 -> 第一半部分的第一个数=-3 -> 第二半部分的第一个数=6 -> 第一半部分的第二个数=-7 -> 第二半部分的第二个数=8，... 你得到：1、-3、6、-7、8、-9、14 - barca_d
@PeterDuniho 是的，我已经提到了。 - Mudassir Hasan
3个回答
14

基本上，我们将有两个指针，一个指向数组的末尾，另一个指向开头。

  v                   v
{-9, -7, -3, 1, 6, 8, 14}

我们比较我们指向的2个数字的绝对值，并将较大的数字插入到新的排序数组中。因此，在这里，它将是14。

New array: {14}

然后，我们将所选项目的头部移动到更靠近中心的位置。因此，在这里，我们将指向14的头部移动到8。

  v                v   
{-9, -7, -3, 1, 6, 8, 14}

然后我们重复这个过程，将绝对值较大的那个数插入到新的已排序数组的开头。在这里，绝对值较大的数是-9，因为|-9| > |8| 

New array: {-9, 14}

然后我们再次移动头部：

      v            v        
{-9, -7, -3, 1, 6, 8, 14}

反复执行直到两个头在中心相遇

不错，当然你可以直接从末尾合并 - 跳过查找枢轴。干得好！ - Thomas Jungblut
2

让我们以你的例子为例：

{-9,-7,-3,1,6,8,14}

你可以将此重写成两个部分：
{-9,-7,-3} and {1,6,8,14}

两个明显的观察点：

  • 左边部分是按降序排列的
  • 右边部分是按升序排列的

现在基本上只需合并这两个已排序子数组，可能需要线性时间。可以查看此处的算法如何将两个已排序的数组合并成一个已排序的数组？。

由于您没有将这些数组拆分，因此需要找到数组中翻转为正值的点。从该分割点开始，您可以一次索引一个地重构已排序的数组，直到数组的边界。

1
如评论所提到的，您基本上正在查看合并排序。原始数据已经排序，所以您只需要按照绝对值从负数和正数数字集中按顺序检索值，并将它们合并。

代码应该如下所示：

int[] input = { -9, -7, -3, 1, 6, 8, 14 };
int[] output = new int[input.Length];
int negativeIndex, positiveIndex = 0, outputIndex = 0;

while (input[positiveIndex] < 0)
{
    positiveIndex++;
}

negativeIndex = positiveIndex - 1;

while (outputIndex < output.Length)
{
    if (negativeIndex < 0)
    {
        output[outputIndex++] = input[positiveIndex++];
    }
    else if (positiveIndex >= input.Length)
    {
        output[outputIndex++] = input[negativeIndex--];
    }
    else
    {
        output[outputIndex++] = -input[negativeIndex] < input[positiveIndex] ?
          input[negativeIndex--] : input[positiveIndex++];
    }
}

上面的方法我认为比较容易理解，但正如其他答案所指出的那样，你甚至可以通过从另一端进行排序而无需扫描数据的 0 点。具体代码如下：
int[] output = new int[input.Length];
int negativeIndex =  0, positiveIndex = input.Length -1, outputIndex = input.Length - 1;

while (outputIndex >= 0)
{
    if (input[negativeIndex] >= 0)
    {
        output[outputIndex--] = input[positiveIndex--];
    }
    else if (input[positiveIndex] < 0)
    {
        output[outputIndex--] = input[negativeIndex++];
    }
    else
    {
        output[outputIndex--] = -input[negativeIndex] < input[positiveIndex] ?
            input[positiveIndex--] : input[negativeIndex++];
    }
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接