954. 二倍数对数组

🟠   🔖  贪心 数组 哈希表 排序  🔗 力扣 LeetCode

题目

Given an integer array of even length arr, return true if it is possible to reorderarr such thatarr[2 * i + 1] = 2 * arr[2 * i] for every0 <= i < len(arr) / 2 , orfalse otherwise.

Example 1:

Input: arr = [3,1,3,6]

Output: false

Example 2:

Input: arr = [2,1,2,6]

Output: false

Example 3:

Input: arr = [4,-2,2,-4]

Output: true

Explanation: We can take two groups, [-2,-4] and [2,4] to form [-2,-4,2,4] or [2,4,-2,-4].

Constraints:

• 2 <= arr.length <= 3 * 10^4
• arr.length is even.
• -10^5 <= arr[i] <= 10^5

题目大意

给定一个长度为偶数的整数数组 arr，只有对 arr 进行重组后可以满足 “对于每个 0 <= i < len(arr) / 2，都有 arr[2 * i + 1] = 2 * arr[2 * i]” 时，返回 true；否则，返回 false。

解题思路

1. 统计频次
   先使用 Map 统计每个元素的出现次数。

2. 排序
   考虑到 x 为负数的情况，对 arr 进行 按绝对值升序 排序，以保证 x 总是先处理，而 2 * x 还未被处理。

3. 贪心匹配
   遍历排序后的 nums（去重后），对于每个 num：

   • 检查 num 是否有足够的 2 * num 进行配对。
   • 若不满足，则返回 false。
   • 否则，减少 2 * num 的计数（因为 2 * num 也有可能作为 x 去和后续的 2 * x 配对）。

复杂度分析

• 时间复杂度: O(n log n)
  • 排序：O(n log n)。
  • 遍历整个二维数组并哈希查找：O(n)。
  • 总复杂度：O(n log n)
• 空间复杂度: O(n)，使用了一个哈希表来统计数字的频率。

代码

/**
 * @param {number[]} arr
 * @return {boolean}
 */
var canReorderDoubled = function (arr) {
	const count = new Map();
	for (let num of arr) {
		count.set(num, (count.get(num) || 0) + 1);
	}

	//  取出去重后的数字，并按照绝对值排序
	const nums = [...count.keys()].sort((a, b) => Math.abs(a) - Math.abs(b));

	for (let num of nums) {
		// 无法找到足够的 2 * num 与 num 配对
		if ((count.get(num * 2) || 0) < count.get(num)) return false;

		count.set(num * 2, (count.get(num * 2) || 0) - count.get(num));
	}
	return true;
};

相关题目

题号	标题	题解	标签	难度	力扣
2007	从双倍数组中还原原数组		贪心 数组 哈希表 1+	🟠	🀄️ 🔗