如何从数组的随机洗牌中获取原始数组

Question

我今天在接受采访时被问到以下问题。我给出了 O(nlgn) 解，但我被要求给出 O(n) 解。我无法想出 O(n) 的解决方案。你能帮我吗？

An input array is given like [1,2,4] then every element of it is doubled and 
appended into the array. So the array now looks like [1,2,4,2,4,8].  How 
this array is randomly shuffled. One possible random arrangement is 
[4,8,2,1,2,4].  Now we are given this random shuffled array and we want to
 get original array [1,2,4] in O(n) time.

The original array can be returned in any order. How can I do it?

Answer 1

我有一个简单的想法，可能不是最好的，但我想不出它不起作用的情况。使数组A具有双倍元素并随机洗牌，保留辅助映射。处理数组的每个元素，每次找到新元素时，将其添加到值为 0 的映射中。处理元素时，递增map[i]和递减map[2*i]。接下来，您将迭代映射并打印值大于零的元素。

一个简单的例子，假设向量是：

[1, 2, 3]

加倍/打乱后的版本是：

A = [3, 2, 1, 4, 2, 6]

处理3时，首先将键3和6添加到值为零的映射中。递增map[3]和递减map[6]。这样，map[3] = 1并且map[6] = -1. 然后是下一个元素map[2] = 1，map[4] = -1依此类推。本例中地图的最终状态为map[1] = 1, map[2] = 1, map[3] = 1, map[4] = -1, map[6] = 0, map[8] = -1, map[12] = -1。

然后，您只需处理映射的键，并对每个值大于零的键将其添加到输出中。当然还有更有效的解决方案，但这个是O(n)。