954.二倍数对数组

二倍数对数组

给定一个整数数组 arr，判断是否可以重新排列 arr 使得对于每个索引 i，arr[2i+1] = 2 * arr[2i]。

示例 1:

输入：arr = [3,1,3,6]
输出：false

示例 2:

输入：arr = [2,1,2,6]
输出：false

示例 3:

输入：arr = [4,-2,2,-4]
输出：true

提示:

• 2 <= arr.length <= 30000
• arr.length 为偶数
• -10^5 <= arr[i] <= 10^5

解析

使用哈希表计数，按绝对值排序后贪心匹配。

var canReorderDoubled = function (arr) {
  const count = new Map();
  for (const x of arr) {
    count.set(x, (count.get(x) || 0) + 1);
  }

  const sorted = [...arr].sort((a, b) => Math.abs(a) - Math.abs(b));

  for (const x of sorted) {
    if (count.get(x) === 0) continue;
    if (count.get(x * 2) === undefined || count.get(x * 2) === 0) {
      return false;
    }
    count.set(x, count.get(x) - 1);
    count.set(x * 2, count.get(x * 2) - 1);
  }

  return true;
};

时间复杂度 O(N log N)，空间复杂度 O(N)。