我最近遇到了一个面向软件工程师的微软面试问题.
给定一组正负整数,重新排列它,使得一端为正整数,另一端为负整数,但保留原始数组中的出现顺序.
例如,给出[1, 7, -5, 9, -12, 15]
的答案是:[-5, -12, 1, 7, 9, 15]
这应该在O(n)中完成.
我们可以很容易地在O(n)中完成它,但我无法想象我们如何能够像原始数组一样维护元素的顺序.如果我们忘记O(n)的复杂性,有人可以告诉我如何在不考虑空间和时间复杂性的情况下保持元素的顺序.
编辑:在实际问题中,我们还需要具有O(1)空间复杂度.