给定一组正整数和负整数，重新排列它，以便一端为正整数，另一端为负整数 [英] Given an array of positive and negative integers, re-arrange it so that you have positive integers on one end and negative integers on other

问题描述

我最近遇到了微软软件工程师面试问题.

I recently came across a Microsoft Interview Question for Software Engineer.

给定一个正整数和负整数数组，重新排列它，使一端为正整数，另一端为负整数，但保留它们在原始数组中的出现顺序.

Given an array of positive and negative integers, re-arrange it so that you have positive integers on one end and negative integers on other, but retain their order of appearance in the original array.

例如，给定 [1, 7, -5, 9, -12, 15]
答案是:[-5, -12, 1, 7, 9, 15]

这应该以 O(n) 时间复杂度和 O(1) 空间复杂度完成.

This should be done in O(n) time complexity and O(1) space complexity.

我们可以在 O(n) 时间复杂度内轻松完成，但我无法考虑如何像在原始数组中一样保持元素的顺序.如果我们忘记 O(n) 复杂度，有人能告诉我如何在不考虑空间和时间复杂度的情况下保持元素的顺序.

We could easily do it in O(n) time complexity, but I am not able to think how we can maintain the order of elements as in original array. If we forget about O(n) complexity, could someone tell me how we can preserve the order of elements without taking into consideration the space- and time-complexity.

推荐答案

要在恒定空间(但二次时间)中实现此结果，可以使用双队列方法，在数组的每一端放置一个队列(类似到荷兰国旗算法).从左到右读取项目:将项目添加到左侧队列意味着不理会它，将项目添加到右侧队列意味着将不在队列中的所有元素向左移动一个并将添加的项目放在最后.然后，要连接队列，只需颠倒第二个队列中元素的顺序即可.

To achieve this result in constant space (but quadratic time), you can use the two-queue approach by placing one queue at each end of the array (similar to the Dutch National Flag algorithm). Read items left-to-right : adding an item to the left queue means leaving it alone, adding an item to the right queue means shifting all elements not in a queue to the left by one and placing the added item at the end. Then, to concatenate the queues, simply reverse the order of elements in the second queue.

这将执行 O(n) 操作(向左移动元素)最多 O(n) 次，从而产生 O(n²) 运行时间.

This performs an O(n) operation (shifting elements left) up to O(n) times, which yields an O(n²) running time.

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

By using a method similar to merge sort, you can achieve a lower O(n log n) complexity: slice the array in two halves, recursively sort them in the form [N P] [N P] then swap the first P with the second N in O(n) time (it gets a bit tricky when they don't have exactly the same size, but it's still linear).

我完全不知道如何将其降低到 O(n) 时间.

I have absolutely no idea of how to get this down to O(n) time.

EDIT:实际上，您的链接列表洞察力是正确的.如果数据以双向链表的形式提供，可以在O(n)时间，O(1)空间内实现双队列策略:

EDIT: actually, your linked list insight is right. If the data is provided as a doubly linked list, you can implement the two-queue strategy in O(n) time, O(1) space:

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).至于空间，没有任何操作分配任何内存(append只是使用pop释放的内存)，所以总体来说是O(1).

With a linked list implementation that keeps pointers to the first and last elements, then pop, append and concatenate are all O(1) operations, so the total complexity is O(n). As for space, none of the operations allocate any memory (append merely uses the memory released by pop), so it's O(1) overall.

这篇关于给定一组正整数和负整数，重新排列它，以便一端为正整数，另一端为负整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！