leetcode
leetcode 2001 ~ 2050
数组能形成多少数对

数组能形成多少数对

难度:

标签:

题目描述

代码结果

运行时间: 19 ms, 内存: 16.0 MB


/*
 * 思路:
 * 使用Java Stream API来实现上述逻辑。
 * 1. 使用Collectors.groupingBy收集每个数字的出现次数。
 * 2. 使用mapToInt和sum来计算可以形成的数对数量和剩余的元素个数。
 */
import java.util.Arrays;
import java.util.Map;
import java.util.stream.Collectors;

public class Solution {
    public int[] numberOfPairs(int[] nums) {
        // 使用Collectors.groupingBy收集每个数字的出现次数
        Map<Integer, Long> countMap = Arrays.stream(nums)
            .boxed()
            .collect(Collectors.groupingBy(num -> num, Collectors.counting()));

        int pairs = countMap.values().stream().mapToInt(count -> (int)(count / 2)).sum();
        int leftover = countMap.values().stream().mapToInt(count -> (int)(count % 2)).sum();

        return new int[]{pairs, leftover};
    }
}

解释

方法:

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

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
题解中提到将每个数字的出现次数模2的余数累加以计算剩余元素的数量,这种方法为什么能准确地反映出无法配对的元素数?
当我们对一个数字的出现次数取模2时,结果只能是1或0。如果一个数字出现偶数次(例如2、4、6次等),它能完全配对,模2的结果为0,表示没有剩余元素。如果一个数字出现奇数次(例如1、3、5次等),它配对后将剩下一个元素,模2的结果为1。因此,将所有数字的出现次数模2的结果累加,就能得到总的无法配对的元素数量。这个方法准确地反映了每种数字剩余未配对的个数。
🦆
在计算数对的总数时,为什么是用数组总长度减去剩余元素数量后再除以2,这样的计算方式是否总是准确无误?
数组总长度表示nums中元素的总数。剩余元素数量是指无法配对的单个元素的总数。当从总元素中减去这些单个剩余元素后,剩下的元素数量必然是偶数,因为它们都可以配对。每对元素包含两个元素,因此将这个剩余元素数除以2就得到了配对的总对数。这种计算方法是准确无误的,因为它基于配对的性质,即两个元素形成一对。
🦆
Counter数据结构是如何帮助优化这个问题的解决方案的,它在这里的作用是什么?
Counter是一个来自collections模块的特殊类型的字典,它用于计数对象元素的出现次数。在这个问题中,使用Counter可以快速统计数组中每个数字出现的次数。这种统计是解决问题的关键步骤,因为我们需要知道每个元素可以形成多少对。Counter简化了计数过程,使得我们不必手动实现计数逻辑,提高了代码的效率和可读性。
🦆
如果输入数组`nums`为空,题解的方法是否仍然适用,算法会返回什么结果?
如果输入数组`nums`为空,题解的方法仍然适用。在这种情况下,Counter对象将为空,因为没有元素来统计。遍历一个空的Counter对象的values()将不会执行任何操作,因此剩余元素的数量`r`将保持为0。最终,算法将返回[0, 0],表示没有数对也没有剩余的单个数字,这是准确的结果。

相关问题