2341.md

title	description	keywords
2341. 数组能形成多少数对	LeetCode 2341. 数组能形成多少数对题解，Maximum Number of Pairs in Array，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 2341. 数组能形成多少数对 数组能形成多少数对 Maximum Number of Pairs in Array 解题思路 数组 哈希表 计数

2341. 数组能形成多少数对

🟢 Easy  🔖  数组 哈希表 计数  🔗 力扣 LeetCode

题目

You are given a 0-indexed integer array nums. In one operation, you may do the following:

• Choose two integers in nums that are equal.
• Remove both integers from nums, forming a pair.

The operation is done on nums as many times as possible.

Return _a 0-indexed integer array _answer of size2 whereanswer[0]is the number of pairs that are formed andanswer[1]is the number of leftover integers innums after doing the operation as many times as possible.

Example 1:

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

Output: [3,1]

Explanation:

Form a pair with nums[0] and nums[3] and remove them from nums. Now, nums = [3,2,3,2,2].

Form a pair with nums[0] and nums[2] and remove them from nums. Now, nums = [2,2,2].

Form a pair with nums[0] and nums[1] and remove them from nums. Now, nums = [2].

No more pairs can be formed. A total of 3 pairs have been formed, and there is 1 number leftover in nums.

Example 2:

Input: nums = [1,1]

Output: [1,0]

Explanation: Form a pair with nums[0] and nums[1] and remove them from nums. Now, nums = [].

No more pairs can be formed. A total of 1 pair has been formed, and there are 0 numbers leftover in nums.

Example 3:

Input: nums = [0]

Output: [0,1]

Explanation: No pairs can be formed, and there is 1 number leftover in nums.

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

题目大意

给你一个下标从 0 开始的整数数组 nums 。在一步操作中，你可以执行以下步骤：

• 从 nums 选出 两个 相等的 整数
• 从 nums 中移除这两个整数，形成一个 数对

请你在 nums 上多次执行此操作直到无法继续执行。

返回一个下标从 0 开始、长度为 2 的整数数组 answer 作为答案，其中 answer[0] 是形成的数对数目，answer[1] 是对 nums 尽可能执行上述操作后剩下的整数数目。

示例 1：

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

输出：[3,1]

解释：

nums[0] 和 nums[3] 形成一个数对，并从 nums 中移除，nums = [3,2,3,2,2] 。

nums[0] 和 nums[2] 形成一个数对，并从 nums 中移除，nums = [2,2,2] 。

nums[0] 和 nums[1] 形成一个数对，并从 nums 中移除，nums = [2] 。

无法形成更多数对。总共形成 3 个数对，nums 中剩下 1 个数字。

示例 2：

输入： nums = [1,1]

输出：[1,0]

解释： nums[0] 和 nums[1] 形成一个数对，并从 nums 中移除，nums = [] 。

无法形成更多数对。总共形成 1 个数对，nums 中剩下 0 个数字。

示例 3：

输入： nums = [0]

输出：[0,1]

解释： 无法形成数对，nums 中剩下 1 个数字。

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

解题思路

1. 统计每个数字的出现频率：

   • 使用一个 Map 作为哈希表，记录数组中每个数字出现的次数。
   • 遍历 nums，对于每个数字，将其频率累加。

2. 计算未被配对的数字数量：

   • 使用一个变量 leftover 记录数组中未被配对的数字数量。
   • 遍历 Map 中每个数字的频率：
     • 如果频率是奇数，则说明该数字中有一个未被配对，累加到 leftover。

3. 计算最多的数对数量：

   • 数组中数字的总个数减去未被配对的数字数，再除以 2，即可得到成对数量 pairs。

4. 返回结果：

   • 将 [pairs, leftover] 作为结果返回。

复杂度分析

• 时间复杂度：O(n + k)
  • 遍历数组统计频率，时间复杂度为 O(n)。
  • 遍历频率表，时间复杂度为 O(k)，其中 k 是数字种类的数量。
  • 总复杂度：O(n + k)。
• 空间复杂度：O(n)，使用了一个哈希表，最坏情况下需要存储 n 个不同的数字。

代码

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var numberOfPairs = function (nums) {
	let freq = new Map();
	for (let num of nums) {
		freq.set(num, (freq.get(num) || 0) + 1);
	}
	let leftover = 0;
	for (let value of freq.values()) {
		if (value % 2 == 1) {
			leftover++;
		}
	}
	return [(nums.length - leftover) / 2, leftover];
};

相关题目

题号	标题	题解	标签	难度	力扣
451	根据字符出现频率排序	[✓]	哈希表 字符串 桶排序 3+	🟠	🀄️ 🔗
692	前K个高频单词		字典树 哈希表 字符串 4+	🟠	🀄️ 🔗
1636	按照频率将数组升序排序	[✓]	数组 哈希表 排序	🟢	🀄️ 🔗