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。

解题思路

• 用一个哈希表 count 来统计 arr 中每个数字的个数，即 count[x] 表示 arr 中 x 的个数；
• 用一个数组 vals 表示去重后的所有数字，并将其按绝对值从小到大排序；
• 遍历 vals，假设 x 为 arr 中绝对值最小的元素，由于没有绝对值比 x 更小的数，因此 x 只能与 2x 匹配。
• 如果此时 count[2x]<count[x]，那么会有部分 x 无法找到它的另一半，即无法满足题目要求；
• 否则将所有 x 和 count[x] 个 2x 从 arr 中去掉，继续判断剩余元素是否满足题目要求。
• 不断重复此操作，如果某个时刻 arr 为空，则说明 arr 可以满足题目要求。

代码

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

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

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

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

相关题目

题号	标题	题解	标签	难度
2007	从双倍数组中还原原数组		贪心 数组 哈希表 1+