leetcode
leetcode 1151 ~ 1200
独一无二的出现次数

独一无二的出现次数

难度:

标签:

题目描述

代码结果

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


/*
 * 思路:
 * 1. 使用流操作统计每个元素的出现次数。
 * 2. 使用一个集合来存储每个出现次数,如果添加失败,则说明出现次数不是唯一的,返回false。
 * 3. 如果遍历结束后,所有出现次数都是唯一的,返回true。
 */

import java.util.Arrays;
import java.util.HashSet;
import java.util.Map;
import java.util.stream.Collectors;

public class UniqueOccurrencesStream {
    public boolean uniqueOccurrences(int[] arr) {
        Map<Integer, Long> countMap = Arrays.stream(arr)
                                             .boxed()
                                             .collect(Collectors.groupingBy(e -> e, Collectors.counting()));
        HashSet<Long> occurrences = new HashSet<>();
        return countMap.values().stream().allMatch(occurrences::add);
    }

    public static void main(String[] args) {
        UniqueOccurrencesStream solution = new UniqueOccurrencesStream();
        int[] arr1 = {1, 2, 2, 1, 1, 3};
        System.out.println(solution.uniqueOccurrences(arr1)); // true
        int[] arr2 = {1, 2};
        System.out.println(solution.uniqueOccurrences(arr2)); // false
        int[] arr3 = {-3, 0, 1, -3, 1, 1, 1, -3, 10, 0};
        System.out.println(solution.uniqueOccurrences(arr3)); // true
    }
}

解释

方法:

这个题解通过一个字典来统计每个数在数组中的出现次数。每次遍历到一个数,如果这个数已经存在于字典中,则将其对应的值加1;如果不存在,则初始化其值为1。之后,这个解法利用集合来检查所有的出现次数是否唯一。将字典的值(即每个数字的出现次数)转化为一个集合,如果集合的大小与字典中值的数量相同,则说明没有重复的出现次数,返回true;否则,返回false。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
题解中使用了字典和集合两种数据结构,能否详细解释它们在此算法中各自的作用和优势?
在这个算法中,字典用于统计每个数字的出现次数。其优势在于提供了快速的查找和更新操作,时间复杂度为O(1),这使得遍历数组并更新出现次数变得高效。每个数字作为键,其出现次数作为值,如果数字已存在于字典中,更新其计数,否则将其添加到字典。集合则用于检查出现次数的唯一性。将字典中所有的值(出现次数)转换到一个集合中,由于集合自动去重,它的大小如果与字典中的值数量相同,说明没有重复的出现次数。集合的优势在于它可以迅速地去除重复元素,并能在O(1)的时间复杂度内完成元素的查找和插入操作。
🦆
解法中提到集合的大小与字典中值的数量相同则返回true,这种方法是否能处理所有边界情况,比如数组为空或数组只有一个元素的情况?
此方法能够有效处理包括数组为空或只有一个元素的边界情况。当数组为空时,字典也将为空,因此字典中的值的数量和集合的大小都是0,满足条件返回true。当数组只有一个元素时,该元素的出现次数为1,字典中将只有一个键值对,其值也为1,因此集合大小和字典的值数量均为1,同样满足条件返回true。因此,这种方法是完备的,可以处理所有边界情况。
🦆
如果在统计过程中发现某两个数字的出现次数相同,是否有更快的方法提前结束程序执行?
可以优化算法以提前结束程序执行。具体方法是在遍历数组的同时,维护一个集合来存储已经出现的次数。每次更新字典中某个数字的出现次数后,首先检查这个新的出现次数是否已经在集合中存在。如果存在,说明已经有至少两个数字具有相同的出现次数,可以立即返回false。如果不存在,将这个新的出现次数添加到集合中。这种方法可以在确定不可能有唯一出现次数时立即停止执行,从而提高算法效率。

相关问题