Question

2007. 从双倍数组中还原原数组

English Version

题目描述

一个整数数组 original 可以转变成一个 双倍 数组 changed ，转变方式为将 original 中每个元素 值乘以 2 加入数组中，然后将所有元素 随机打乱 。

给你一个数组 changed ，如果 change 是 双倍 数组，那么请你返回 original数组，否则请返回空数组。original 的元素可以以 任意 顺序返回。

 

示例 1：

输入：changed = [1,3,4,2,6,8]
输出：[1,3,4]
解释：一个可能的 original 数组为 [1,3,4] :
- 将 1 乘以 2 ，得到 1 * 2 = 2 。
- 将 3 乘以 2 ，得到 3 * 2 = 6 。
- 将 4 乘以 2 ，得到 4 * 2 = 8 。
其他可能的原数组方案为 [4,3,1] 或者 [3,1,4] 。

示例 2：

输入：changed = [6,3,0,1]
输出：[]
解释：changed 不是一个双倍数组。

示例 3：

输入：changed = [1]
输出：[]
解释：changed 不是一个双倍数组。

 

提示：

• 1 <= changed.length <= 105
• 0 <= changed[i] <= 105

解法

方法一：排序 + 计数 + 遍历

我们先判断数组 changed 的长度 $n$ 是否为奇数，若是，则直接返回空数组。

然后对数组 changed 进行排序，并且用哈希表或数组 cnt 统计数组 changed 中每个元素出现的次数。

接下来遍历数组 changed，对于数组 changed 中的每个元素 $x$，我们首先判断哈希表 cnt 中是否存在 $x$，若不存在，则直接跳过该元素。否则，我们判断 cnt 中是否存在 $x \times 2$，若不存在，则直接返回空数组。否则，我们将 $x$ 加入答案数组 ans 中，并且将 cnt 中 $x$ 和 $x \times 2$ 的出现次数分别减 $1$。

遍历结束后，我们判断答案数组 ans 的长度是否为 $\frac{n}{2}$，若是，则返回 ans，否则返回空数组。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 changed 的长度。

class Solution:
  def findOriginalArray(self, changed: List[int]) -> List[int]:
    n = len(changed)
    if n & 1:
      return []
    cnt = Counter(changed)
    changed.sort()
    ans = []
    for x in changed:
      if cnt[x] == 0:
        continue
      if cnt[x * 2] <= 0:
        return []
      ans.append(x)
      cnt[x] -= 1
      cnt[x * 2] -= 1
    return ans if len(ans) == n // 2 else []

class Solution {
  public int[] findOriginalArray(int[] changed) {
    int n = changed.length;
    if (n % 2 == 1) {
      return new int[] {};
    }
    Arrays.sort(changed);
    int[] cnt = new int[changed[n - 1] + 1];
    for (int x : changed) {
      ++cnt[x];
    }
    int[] ans = new int[n / 2];
    int i = 0;
    for (int x : changed) {
      if (cnt[x] == 0) {
        continue;
      }
      if (x * 2 >= cnt.length || cnt[x * 2] <= 0) {
        return new int[] {};
      }
      ans[i++] = x;
      cnt[x]--;
      cnt[x * 2]--;
    }
    return i == n / 2 ? ans : new int[] {};
  }
}

class Solution {
public:
  vector<int> findOriginalArray(vector<int>& changed) {
    int n = changed.size();
    if (n & 1) {
      return {};
    }
    sort(changed.begin(), changed.end());
    vector<int> cnt(changed.back() + 1);
    for (int& x : changed) {
      ++cnt[x];
    }
    vector<int> ans;
    for (int& x : changed) {
      if (cnt[x] == 0) {
        continue;
      }
      if (x * 2 >= cnt.size() || cnt[x * 2] <= 0) {
        return {};
      }
      ans.push_back(x);
      --cnt[x];
      --cnt[x * 2];
    }
    return ans.size() == n / 2 ? ans : vector<int>();
  }
};

func findOriginalArray(changed []int) []int {
  n := len(changed)
  ans := []int{}
  if n&1 == 1 {
    return ans
  }
  sort.Ints(changed)
  cnt := make([]int, changed[n-1]+1)
  for _, x := range changed {
    cnt[x]++
  }
  for _, x := range changed {
    if cnt[x] == 0 {
      continue
    }
    if x*2 >= len(cnt) || cnt[x*2] <= 0 {
      return []int{}
    }
    ans = append(ans, x)
    cnt[x]--
    cnt[x*2]--
  }
  if len(ans) != n/2 {
    return []int{}
  }
  return ans
}

function findOriginalArray(changed: number[]): number[] {
  const n = changed.length;
  if (n & 1) {
    return [];
  }
  const cnt = new Map<number, number>();
  for (const x of changed) {
    cnt.set(x, (cnt.get(x) || 0) + 1);
  }
  changed.sort((a, b) => a - b);
  const ans: number[] = [];
  for (const x of changed) {
    if (cnt.get(x) == 0) {
      continue;
    }
    if ((cnt.get(x * 2) || 0) <= 0) {
      return [];
    }
    ans.push(x);
    cnt.set(x, (cnt.get(x) || 0) - 1);
    cnt.set(x * 2, (cnt.get(x * 2) || 0) - 1);
  }
  return ans.length == n / 2 ? ans : [];
}