Easy

题目描述

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

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

对数组 nums 执行上述操作 尽可能多 的次数。

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

示例 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. 频次统计：首先统计数组中每个数字的出现次数。对于每个数字，其能形成的数对数量等于 频次 / 2（整数除法）。

  2. 计算结果：

    • 数对总数：所有数字能形成的数对数量之和
    • 剩余数字：所有数字频次为奇数的数量之和，也等于 总数字数量 - 数对数量 * 2

  3. 实现方案：

    • 哈希表法：使用哈希表统计频次，遍历计算结果
    • 数组法：由于数字范围小（0-100），可以用数组代替哈希表，效率更高

推荐使用数组法，因为数据范围较小且访问效率更高。

时间复杂度：O(n)，其中 n 是数组长度 空间复杂度：O(1)，使用固定大小的计数数组

代码实现

class Solution {
public:
    vector<int> numberOfPairs(vector<int>& nums) {
        int count[101] = {0};
        
        // 统计每个数字的频次
        for (int num : nums) {
            count[num]++;
        }
        
        int pairs = 0;
        int leftover = 0;
        
        // 计算数对数量和剩余数量
        for (int i = 0; i <= 100; i++) {
            pairs += count[i] / 2;
            leftover += count[i] % 2;
        }
        
        return {pairs, leftover};
    }
};

class Solution:
    def numberOfPairs(self, nums: List[int]) -> List[int]:
        from collections import Counter
        
        count = Counter(nums)
        pairs = 0
        leftover = 0
        
        for freq in count.values():
            pairs += freq // 2
            leftover += freq % 2
            
        return [pairs, leftover]

public class Solution {
    public int[] NumberOfPairs(int[] nums) {
        int[] count = new int[101];
        
        // 统计每个数字的频次
        foreach (int num in nums) {
            count[num]++;
        }
        
        int pairs = 0;
        int leftover = 0;
        
        // 计算数对数量和剩余数量
        for (int i = 0; i <= 100; i++) {
            pairs += count[i] / 2;
            leftover += count[i] % 2;
        }
        
        return new int[] {pairs, leftover};
    }
}

var numberOfPairs = function(nums) {
    const count = new Array(101).fill(0);
    
    // 统计每个数字的频次
    for (const num of nums) {
        count[num]++;
    }
    
    let pairs = 0;
    let leftover = 0;
    
    // 计算数对数量和剩余数量
    for (let i = 0; i <= 100; i++) {
        pairs += Math.floor(count[i] / 2);
        leftover += count[i] % 2;
    }
    
    return [pairs, leftover];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n)
空间复杂度O(1)

其中 n 是数组 nums 的长度。空间复杂度为 O(1) 是因为使用了固定大小的计数数组（101个元素）。

相关题目