给定正负整数数组，请重新排列，以便一端有正整数，另一端有负整数

Question

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

给定正负整数数组，请重新排列它，以便一端具有正整数，另一端具有负整数， 但在原始数组中保留其出现顺序。

例如，给出[1, 7, -5, 9, -12, 15]
的答案将是：[-5, -12, 1, 7, 9, 15]

这应该在O（n）中完成。

我们可以很容易地在O（n）中做到这一点，但我无法思考如何像原始数组中那样维护元素的顺序。如果我们忘记O（n）的复杂性，有人可以告诉我如何在不考虑空间和时间复杂性的情况下保留元素的顺序。

编辑 ：在实际问题中，我们还必须具有O（1）空间复杂度。

Answer 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和concatenate都是O（1）操作，因此总复杂度为O（n）。至于空间，没有任何操作分配任何内存（仅使用pop释放的内存），因此总体上为O（1）。