2341. 数组能形成多少数对

🟢   🔖  数组 哈希表 计数  🔗 力扣 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 size2whereanswer[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	按照频率将数组升序排序	[✓]	数组 哈希表 排序	🟢	🀄️ 🔗