题目描述

给你一个整数数组 arr，请你帮忙统计数组中每个数的出现次数。

如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。

样例

输入：arr = [1,2,2,1,1,3]
输出：true
解释：在该数组中，1 出现了 3 次，2 出现了 2 次，3 只出现了 1 次。没有两个数的出现次数相同。

输入：arr = [1,2]
输出：false

输入：arr = [-3,0,1,-3,1,1,1,-3,10,0]
输出：true

限制

• 1 <= arr.length <= 1000
• -1000 <= arr[i] <= 1000

算法

(哈希表) $O(n)$

1. 用一个 unordered_map 统计数组中每个数字的出现次数。
2. 然后枚举这个哈希表中的所有元素，将出现的次数放到 unordered_set 中，如果过程中出现了重复，则返回 false。
3. 否则，最后返回 true。

时间复杂度

• 每个数字仅遍历一次，故时间复杂度为 $O(n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间记录每个数字出现的次数。

C++ 代码

class Solution {
public:
    bool uniqueOccurrences(vector<int>& arr) {
        int n = arr.size();
        unordered_map<int, int> vis;
        unordered_set<int> dup;

        for (int i = 0; i < n; i++)
            vis[arr[i]]++;

        for (const auto &it : vis) {
            if (dup.find(it.second) != dup.end())
                return false;
            dup.insert(it.second);
        }

        return true;
    }
};