leetcode
leetcode 1551 ~ 1600
唯一元素的和

唯一元素的和

难度:

标签:

题目描述

代码结果

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


/*
 * 思路:
 * 使用Java Stream来实现:
 * 1. 首先,使用Collectors.groupingBy统计每个数字出现的次数。
 * 2. 然后,过滤出出现次数为1的数字,并计算它们的和。
 */
import java.util.Arrays;
import java.util.Map;
import java.util.stream.Collectors;

public class UniqueElementSumStream {
    public int sumOfUnique(int[] nums) {
        // 统计每个数字出现的次数
        Map<Integer, Long> countMap = Arrays.stream(nums)
                .boxed()
                .collect(Collectors.groupingBy(num -> num, Collectors.counting()));
        // 计算只出现一次的数字的和
        return countMap.entrySet().stream()
                .filter(entry -> entry.getValue() == 1)
                .mapToInt(Map.Entry::getKey)
                .sum();
    }

    public static void main(String[] args) {
        UniqueElementSumStream solution = new UniqueElementSumStream();
        int[] nums1 = {1, 2, 3, 2};
        int[] nums2 = {1, 1, 1, 1, 1};
        int[] nums3 = {1, 2, 3, 4, 5};
        System.out.println(solution.sumOfUnique(nums1)); // 输出:4
        System.out.println(solution.sumOfUnique(nums2)); // 输出:0
        System.out.println(solution.sumOfUnique(nums3)); // 输出:15
    }
}

解释

方法:

本题解采用哈希表来统计数组中每个元素出现的次数。通过Python的Counter类,首先统计数组nums中每个元素的出现次数。然后遍历这个计数哈希表,只将出现次数为1的元素相加,得到所有唯一元素的和。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么选择哈希表来处理这个问题,而不是其他数据结构如数组或链表?
哈希表(或字典)提供了非常高效的元素查找、插入和更新操作,这些操作的平均时间复杂度为O(1)。在解决问题时,需要频繁地检查和更新元素的出现次数。使用数组虽然也可以实现,但当元素范围很大或不是连续的时,会导致空间浪费或数组索引处理复杂。链表对于这种需要频繁查找的操作效率较低,因为其查找操作的时间复杂度为O(n)。因此,哈希表是处理此类问题的最佳数据结构,既能保证效率,也能节省空间。
🦆
在统计元素出现次数时,Counter类的内部实现是如何确保准确且高效统计的?
Counter类是Python collections模块中的一个特殊的字典类,它的内部实现基于哈希表。它为每个元素建立一个键,并将该元素出现的次数作为值。每次插入一个元素时,Counter检查元素是否已存在,如果存在则增加该元素的计数,如果不存在则将该元素的计数设置为1。这种实现方式确保了元素计数的准确性和操作的高效性,因为每次更新操作仅需O(1)的时间复杂度。
🦆
在处理极端情况,如所有元素都是唯一的或没有唯一的元素时,这种方法的表现如何?
在所有元素都是唯一的情况下,Counter会为每个元素记录一次出现,遍历这些元素并累加结果时将得到整个数组的和,这种情况下方法依然有效且效率高。如果没有唯一的元素,即每个元素至少出现两次,那么在遍历计数哈希表时,不会有元素的计数为1,因此返回的和将为0。这种方法在这两种极端情况下都能正确处理,并且不需要额外的逻辑判断,显示出其鲁棒性和效率。

相关问题