一、题目描述

Given an array of integers arr, write a function that returns true if
and only if the number of occurrences ofeach value in the array is unique.

Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. 
No two values have the same number of occurrences.

二、题解

解题方案

• HashMap 与 HashSet
• hash 数组

方法一：HashMap 与 HashSet

思路

• 记录每个数字以及相应的出现次数。
• 检查出现次数是否重复。
• 如果每个元素的出现次数都不同，那么将会有 $arr.length$ 种出现次数。

算法

关系到 $hash$ 映射和去重，无疑是富含工具类库的编程语言比较容易解决，思路如下：

• 定义一个 $map$，$key$ 记录每个元素，value 记录元素的出现次数。
• 定义 set 存储 map 的出现次数。
• 如果每个元素的出现次数都不同，那么 $set$ 中将会有 $arr.length$ 种出现次数。

public boolean uniqueOccurrences(int[] arr) {
    HashMap<Integer, Integer> elemMap = new HashMap<>();
    for (int n : arr) {     // 统计每个数字出现的次数
        elemMap.put(n, elemMap.getOrDefault(n, 0) + 1);
    }
    HashSet<Integer> set = new HashSet();        // 注：自动拆箱需要一定时间
    for (Integer occurrence : elemMap.values()) {// 检查元素的出现次数
        if (!set.add(occurrence))
        return false;
    }
    return true;
}

复杂度分析

• 时间复杂度：$O(N)$，$N$ 为数组 $arr$ 的元素个数。
• 空间复杂度：取决于数组 $arr$ 的元素重复程度。

方法二：hash 数组

思路

• 统计每个数字出现的次数。
• 统计字母的出现次数种类个数。
• 检查出现次数种类的个数。

算法

• 定义哈希数组 $hashArr$ 记录元素的出现次数。
  • 注：由于元素的值可能为负数或正数，我们将负数取反，加上 $1000$，便可与正数区分开。
• 定义数组 $counter$ 将出现次数进行归类。
• 如果存在独一无二的出现次数，$counter$ 数组的所有元素都不大于 $1$。

public boolean uniqueOccurrences(int[] arr) {
    int[] hashArr = new int[2001];
    for (int i = 0; i < arr.length; i++) {    // 统计每个数字出现的次数。
        if (arr[i] < 0) hashArr[1000 + arr[i]] ++;
        else            hashArr[arr[i]] ++;
    }

    int[] counter = new int[2000];
    for (int i = 0; i < counter.length; i++) {// 统计字母的出现次数种类个数。
        if (hashArr[i] != 0)
        counter[hashArr[i]]++;
    }

    for (int i = 0; i < counter.length; i++) {// 检查出现次数种类的个数。
        if (counter[i] > 1)  return false;
    }
    return true;
}

复杂度分析

• 时间复杂度：$O(N)$，$N$ 为数组 $arr$ 的元素个数。
• 空间复杂度：$O(1)$，使用了常数级别的空间。

最后

以上就是现实镜子为你收集整理的【数论】C021_独一无二的出现次数（Hash 数组 || Map+Set）一、题目描述二、题解的全部内容，希望文章能够帮你解决【数论】C021_独一无二的出现次数（Hash 数组 || Map+Set）一、题目描述二、题解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。