唯一类别的数量
难度:
标签:
题目描述
代码结果
运行时间: 1214 ms, 内存: 16.7 MB
/*
* LeetCode 2782: Unique Number of Occurrences
* Given an array of integers, write a function that returns the number of unique values in the array.
*
* Approach using Java Streams:
* 1. Use streams to count the frequency of each element in the array and store it in a Map.
* 2. Use a Set to store the frequencies to ensure they are unique.
* 3. If the size of the Set is equal to the number of unique elements in the array, return true; otherwise, return false.
*/
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class SolutionStream {
public boolean uniqueOccurrences(int[] arr) {
// Step 1: Use streams to count the frequency of each element
var frequencyMap = IntStream.of(arr)
.boxed()
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
// Step 2: Use a Set to store the frequencies
var frequencySet = new HashSet<>(frequencyMap.values());
// Step 3: Compare the size of the Set and the frequencyMap values
return frequencySet.size() == frequencyMap.size();
}
}
解释
方法:
该题解的核心思路是使用一个字典来跟踪已知的类别。对于每一个元素i(从0到n-1),检查它是否属于已知的某个类别。这是通过使用categoryHandler的haveSameCategory方法来实现的,该方法可以判断两个元素是否属于同一类别。如果元素i与某个已知类别的代表元素j属于同一类别,那么就将i添加到j代表的类别中。如果i与所有已知类别的代表元素都不同类,那么它就自成一类。最后,字典中的键的数量即为不同类别的总数。
时间复杂度:
O(n^2)
空间复杂度:
O(n)
代码细节讲解
🦆
在算法中,为什么选择使用字典来存储类别,而不是其他数据结构如列表或集合?
▷🦆
算法中当遇到一个新元素i与所有已知类别的代表元素都不同类时,直接将其作为新类别的代表元素。这种方法是否可能在有些情况下导致分类错误?
▷🦆
在算法中,有没有可能存在重复检查同一元素属于多个类别的情况,从而影响效率?
▷