给定一个正整数和负整数数组，重新排列它，以便在一端有正整数，另一端有负整数。

Question

最近我遇到了一个微软软件工程师的面试问题。

给出了一个正整数和负整数数组，重新排列它，以便在一端有正整数，另一端有负整数，但保留它们在原始数组中的出现顺序。

例如，给定[1, 7, -5, 9, -12, 15]

答案是：[-5, -12, 1, 7, 9, 15]

这应该在O(n)时间复杂度和O(1)空间复杂度中完成。

我们可以很容易地在O(n)时间复杂度中做到这一点，但我想不出我们如何能够像在原始数组中那样维持元素的顺序。如果我们忘记了O(n)的复杂性，有人能告诉我如何在不考虑空间和时间复杂性的情况下保持元素的顺序。

Answer 1

为了在恒定的空间(但二次时间)中实现这一结果，您可以使用双队列方法，在数组的两端放置一个队列(类似于荷兰国旗算法)。从左到右读取项目:向左队列中添加项意味着将其单独放置，向右队列添加项意味着将队列中的所有元素左移1，并将添加的项放在末尾。然后，要连接队列，只需反转第二个队列中元素的顺序即可。

这将执行O(n)操作(左移元素)到O(n)次，从而产生O(N)运行时间。

通过使用类似于合并排序的方法，您可以获得更低的O(n log n)复杂度:将数组分成两半，递归地将它们按[N P] [N P]形式排序，然后在O(n)时间内将第一个P与第二个N交换(当它们没有完全相同的大小时，会变得有点棘手，但仍然是线性的)。

我完全不知道如何把它降到O(n)时间。

编辑：实际上，您的链接列表洞察力是正确的。如果数据是作为双链接列表提供的，则可以在O(n)时间O(1)空间内实现两个队列策略：

sort(list):
  negative = empty
  positive = empty
  while (list != empty)
     first = pop(list)
     if (first > 0) 
         append(positive,first)
     else
         append(negative,first)
  return concatenate(negative,positive)

通过链接列表实现来保持指向第一个和最后一个元素的指针，那么pop、append和串联都是O(1)操作，所以总复杂度是O(n)。至于空间，没有一个操作分配任何内存(附加只是使用pop释放的内存)，所以总体上是O(1)。

Answer 2

这里是O(n) time O(1)空间解的一个constriant版本，它假定maxValue*(maxValue+1)小于Integer.MAX_VALUE，其中maxValue是数组中最大值减去最小值的结果。它使用原始数组作为临时数组来存储结果。

public static void specialSort(int[] A){
    int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
    for(int i=0; i<A.length; i++){
        if(A[i] > max)
            max = A[i];
        if(A[i] < min)
            min = A[i];
    }
    //Change all values to Positive
    for(int i=0; i<A.length; i++)
        A[i]-= min;

    int newMax = max-min+1;

    //Save original negative values into new positions
    int currNegativeIndex = 0;
    for(int i=0; i<A.length; i++)
        if(A[i]%newMax < (-min))
            A[currNegativeIndex++] += (A[i]%newMax)*newMax;
    //Save original positive values into new positions
    int currPositiveIndex = currNegativeIndex;
    for(int i=0; i<A.length; i++)
        if(A[i]%newMax > (-min))
            A[currPositiveIndex++] += (A[i]%newMax)*newMax;
    //Recover to original value 
    for(int i=0; i<A.length; i++){
        A[i] = A[i]/newMax + min; 
    }
}

Answer 3

我不确定我是否正确地理解了这个问题，因为答案似乎太简单了：

• 遍历数组并计数负数-O(N)
• 创建一个大小为O(N)
• 的新数组，遍历原始数组并将数字放置到新数组中。使用已知的负数来抵消正数- O(n)

这里有一个用Python快速实现的方法。它与上面的略有不同，首先为底片创建一个数组，然后附加积极的内容。所以它不那么有效，但仍然是O(n)。

>>> a = [1,7,-5,9,-12,15]
>>> print [x for x in a if x < 0] + [y for y in a if y >= 0]
[-5, -12, 1, 7, 9, 15]

编辑:好的，现在O(1)空间压缩变得更难了。我也对如何在O(n)时间复杂度中实现它感兴趣。如果有帮助，这里有一种方法可以保持O(1)空间复杂度，但需要O(n^2)时间复杂度：

• 从最左边的负数开始。遍历数组，直到找到下一个负数为止。
• 在一个新循环中，用它的正数交换负数。这样做，直到你达到其他负数。这将确保数字的顺序保持为unchanged.
• Rince，并在寻找新负数时一直重复到数组的末尾。