我今天在接受采访时被问到以下问题。我给出了 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?