数组能形成多少数对

难度: Easy

给你一个下标从 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

Submission

运行时间: 19 ms

内存: 16.0 MB

class Solution:
    def numberOfPairs(self, nums: List[int]) -> List[int]:
        nc = Counter(nums)
        r = 0
        for n in nc.values():
            r += n%2
            
        return [(len(nums)-r)//2 ,r]

Explain

首先，该题解通过使用Counter来统计nums中每个元素的出现次数。然后，初始化一个变量r用于记录最后数组中剩余的元素数量。对于Counter返回的每个值（即每个数字的出现次数），通过累加其除以2后的余数，即可得到未被配对的元素的数量。最后，返回结果数组，第一个元素是所有数字成对数（即(nums的总长度 - 剩余元素数量)除以2），第二个元素是剩余的单个数字的数量。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def numberOfPairs(self, nums: List[int]) -> List[int]:
        # 使用Counter统计nums中每个数字的出现次数
        nc = Counter(nums)
        # 初始化剩余元素的数量变量r
        r = 0
        # 遍历每个数字的出现次数，统计不能成对的数量
        for n in nc.values():
            r += n % 2
        # 返回数对的总数和剩余的单个数字的数量
        return [(len(nums) - r) // 2, r]

Explore

当我们对一个数字的出现次数取模2时，结果只能是1或0。如果一个数字出现偶数次（例如2、4、6次等），它能完全配对，模2的结果为0，表示没有剩余元素。如果一个数字出现奇数次（例如1、3、5次等），它配对后将剩下一个元素，模2的结果为1。因此，将所有数字的出现次数模2的结果累加，就能得到总的无法配对的元素数量。这个方法准确地反映了每种数字剩余未配对的个数。

数组总长度表示nums中元素的总数。剩余元素数量是指无法配对的单个元素的总数。当从总元素中减去这些单个剩余元素后，剩下的元素数量必然是偶数，因为它们都可以配对。每对元素包含两个元素，因此将这个剩余元素数除以2就得到了配对的总对数。这种计算方法是准确无误的，因为它基于配对的性质，即两个元素形成一对。

Counter是一个来自collections模块的特殊类型的字典，它用于计数对象元素的出现次数。在这个问题中，使用Counter可以快速统计数组中每个数字出现的次数。这种统计是解决问题的关键步骤，因为我们需要知道每个元素可以形成多少对。Counter简化了计数过程，使得我们不必手动实现计数逻辑，提高了代码的效率和可读性。

如果输入数组`nums`为空，题解的方法仍然适用。在这种情况下，Counter对象将为空，因为没有元素来统计。遍历一个空的Counter对象的values()将不会执行任何操作，因此剩余元素的数量`r`将保持为0。最终，算法将返回[0, 0]，表示没有数对也没有剩余的单个数字，这是准确的结果。