LeetCode 每日一题 1207. 独一无二的出现次数

java击败100%的哈希表方法：用数组代替哈希表

普通哈希表

使用哈希表，一遍记录，一遍去重，思路简单。

class Solution {
    public boolean uniqueOccurrences(int[] arr) {
    Map<Integer, Integer> map = new HashMap<>();for(int num : arr) {
    map.put(num, map.getOrDefault(num, 0) + 1);}Set<Integer> set = new HashSet<>();for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
    int value = entry.getValue();if(set.contains(value)) return false;else set.add(value);}return true;}
}

时间复杂度

遍历一遍数组一遍值域$O(n+k)$。

空间复杂度

同理，$O(n+k)$。

加速哈希表

本题数据长度只有不超过1000，并且数据范围为$[?1000,1000]$，因此可以使用数组来代替哈希表记录和去重，访问速度大大加快。

class Solution {
    public boolean uniqueOccurrences(int[] arr) {
    int[] map = new int[2001];for(int num : arr) map[num + 1000]++;boolean[] set = new boolean[1001];for(int i = 0; i < map.length; i++) {
    if(map[i] == 0) continue;if(set[map[i]]) return false;else set[map[i]] = true;}return true;}
}

可以看出速度有了“很大”的提升！

时间复杂度

遍历一遍数组一遍值域$O(n+k)$。

空间复杂度

同理，$O(n+k)$。