面试算法题：如何在O(n)时间复杂度内还原随机打乱的扩展数组的原始数组

Great question! It's tricky to pivot from an O(n log n) sorting-based approach to an O(n) solution, but once you lock into the key observation, it all falls into place. Let's break down the approach step by step:

The original array's elements are exactly the smallest unpaired values in the shuffled array. Here's why: every element in the shuffled array is either from the original set, or double an element from the original set. Since all values are positive integers (implied by the problem examples), the smallest value in the shuffled array can't be a double of any other element (there's nothing smaller to double into it). Once we handle that smallest value, we can eliminate its corresponding doubled value from the frequency count, and repeat the process with the next smallest remaining value.

• Step 1: Count Element Frequencies
  First, we build a frequency map (hash table) to track how many times each number appears in the shuffled array. This takes O(n) time since we iterate through the array once.
  For your example [4,8,2,1,2,4], the frequency map would look like: {1: 1, 2: 2, 4: 2, 8: 1}.

• Step 2: Extract Original Elements
  We repeatedly find the smallest value with a non-zero frequency:

  1. This smallest value is guaranteed to be part of the original array. Add it to our result list.
  2. Decrement its frequency count (remove it from the map if the count hits 0).
  3. Decrement the frequency count of its double (current * 2) as well—this element was added when we doubled the original value, so it doesn't belong in the original array. Remove it from the map if its count hits 0.
  4. Repeat until the frequency map is empty.

  Applying this to your example:

  • Start with the smallest value 1: add to result, remove 1 from the map, and decrement 2's count to 1.
  • Next smallest remaining value is 2: add to result, remove 2 from the map, decrement 4's count to 1.
  • Next smallest remaining value is 4: add to result, remove 4 from the map, decrement 8's count to 0 (so remove 8 too).
  • Result is [1,2,4]—exactly the original array.

from collections import defaultdict

def restore_original(shuffled_arr):
    freq = defaultdict(int)
    for num in shuffled_arr:
        freq[num] += 1
    
    result = []
    # Initialize with the smallest value to start our search
    current_min = min(shuffled_arr)
    
    while freq:
        # Find the next smallest value with non-zero frequency
        while current_min not in freq:
            current_min += 1
        
        original_num = current_min
        result.append(original_num)
        
        # Remove the original num from frequency map
        freq[original_num] -= 1
        if freq[original_num] == 0:
            del freq[original_num]
        
        # Remove its doubled counterpart
        doubled_num = original_num * 2
        if doubled_num in freq:
            freq[doubled_num] -= 1
            if freq[doubled_num] == 0:
                del freq[doubled_num]
    
    return result

# Test with your example
shuffled = [4,8,2,1,2,4]
print(restore_original(shuffled))  # Output: [1,2,4] (order may vary but is valid)

• Building the frequency map is O(n).
• Each element (original and doubled) is processed exactly once—we either remove it from the map or decrement its count once. Even the loop to find the next smallest value doesn't add extra complexity, since each value is checked at most once.
• Hash table operations (add, remove, check existence) are average O(1).

If the original array contains 0, you'll need a minor adjustment: since doubling 0 gives 0, each pair of 0s in the shuffled array corresponds to one 0 in the original array. The rest of the logic stays the same—0 will be the smallest value, and you'll decrement its count by 2 each time instead of 1 (and skip the doubled check, since it's the same as the original).

内容的提问来源于stack exchange，提问作者sachin