2206. 将数组划分成相等数对

🟢   🔖  位运算 数组 哈希表 计数  🔗 力扣 LeetCode

题目

You are given an integer array nums consisting of 2 * n integers.

You need to divide nums into n pairs such that:

• Each element belongs to exactly one pair.
• The elements present in a pair are equal.

Return true if nums can be divided into n pairs, otherwise returnfalse.

Example 1:

Input: nums = [3,2,3,2,2,2]

Output: true

Explanation:

There are 6 elements in nums, so they should be divided into 6 / 2 = 3 pairs.

If nums is divided into the pairs (2, 2), (3, 3), and (2, 2), it will satisfy all the conditions.

Example 2:

Input: nums = [1,2,3,4]

Output: false

Explanation:

There is no way to divide nums into 4 / 2 = 2 pairs such that the pairs satisfy every condition.

Constraints:

• nums.length == 2 * n
• 1 <= n <= 500
• 1 <= nums[i] <= 500

题目大意

给你一个整数数组 nums ，它包含 2 * n 个整数。

你需要将 nums 划分成 n 个数对，满足：

• 每个元素 只属于一个 数对。
• 同一数对中的元素 相等 。

如果可以将 nums 划分成 n 个数对，请你返回 true ，否则返回 false 。

示例 1：

输入： nums = [3,2,3,2,2,2]

输出： true

解释：

nums 中总共有 6 个元素，所以它们应该被划分成 6 / 2 = 3 个数对。

nums 可以划分成 (2, 2) ，(3, 3) 和 (2, 2) ，满足所有要求。

示例 2：

输入： nums = [1,2,3,4]

输出： false

解释：

无法将 nums 划分成 4 / 2 = 2 个数对且满足所有要求。

提示：

• nums.length == 2 * n
• 1 <= n <= 500
• 1 <= nums[i] <= 500

解题思路

1. 统计频率：

   • 使用 Map 数据结构统计每个数字在数组中出现的频率。

2. 检查频率是否为偶数：

   • 遍历所有频率值，判断是否存在奇数频率。
   • 如果存在奇数频率，则无法划分，返回 false；否则返回 true。

3. 优化判定：

   • 直接使用数组的 filter 方法，筛选出所有奇数频率的元素，如果筛选结果长度为 0，则说明所有频率均为偶数。

复杂度分析

• 时间复杂度：O(n)

  • 统计频率的时间复杂度为 O(n)，其中 n 是数组长度。
  • 检查频率的时间复杂度为 O(m)，其中 m 是不同数字的个数。
  • 总时间复杂度为 O(n)（因为通常 m << n）。

• 空间复杂度：O(m)，其中 m 是数组中不同数字的个数，Map 存储所有不同数字的频率。

代码

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var divideArray = function (nums) {
	let freq = new Map();

	// 统计每个数字的频率
	for (let num of nums) {
		freq.set(num, (freq.get(num) || 0) + 1);
	}

	// 检查是否存在奇数频率的数字
	return [...freq.values()].filter((i) => i % 2 != 0).length == 0;
};

相关题目

题号	标题	题解	标签	难度	力扣
1636	按照频率将数组升序排序	[✓]	数组 哈希表 排序	🟢	🀄️ 🔗
3069	将元素分配到两个数组中 I		数组 模拟	🟢	🀄️ 🔗
3072	将元素分配到两个数组中 II		树状数组 线段树 数组 1+	🔴	🀄️ 🔗