Easy

题目描述

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

解题思路

这道题需要判断数组中每个元素的出现次数是否都不相同。我们可以采用两步解决方案：

解题思路

步骤1：统计频次 使用哈希表统计每个元素在数组中的出现次数。遍历数组，对于每个元素，将其作为键，出现次数作为值存储在哈希表中。

步骤2：检查唯一性 将所有出现次数收集起来，检查是否有重复。可以使用集合(Set)来判断：如果出现次数的个数等于去重后的个数，说明所有出现次数都是唯一的。

算法流程：

  1. 创建哈希表统计每个元素的出现次数
  2. 遍历数组，更新哈希表
  3. 提取所有出现次数到集合中
  4. 比较原始次数列表长度与集合长度，相等则返回true，否则返回false

这种方法简洁高效，时间复杂度为O(n)，空间复杂度为O(n)，其中n是数组长度。

代码实现

class Solution {
public:
    bool uniqueOccurrences(vector<int>& arr) {
        unordered_map<int, int> count;
        for (int num : arr) {
            count[num]++;
        }
        
        unordered_set<int> occurrences;
        for (auto& pair : count) {
            if (occurrences.count(pair.second)) {
                return false;
            }
            occurrences.insert(pair.second);
        }
        
        return true;
    }
};

class Solution:
    def uniqueOccurrences(self, arr: List[int]) -> bool:
        from collections import Counter
        
        count = Counter(arr)
        occurrences = list(count.values())
        
        return len(occurrences) == len(set(occurrences))

public class Solution {
    public bool UniqueOccurrences(int[] arr) {
        Dictionary<int, int> count = new Dictionary<int, int>();
        
        foreach (int num in arr) {
            if (count.ContainsKey(num)) {
                count[num]++;
            } else {
                count[num] = 1;
            }
        }
        
        HashSet<int> occurrences = new HashSet<int>();
        foreach (var pair in count) {
            if (!occurrences.Add(pair.Value)) {
                return false;
            }
        }
        
        return true;
    }
}

var uniqueOccurrences = function(arr) {
    const count = new Map();
    
    for (const num of arr) {
        count.set(num, (count.get(num) || 0) + 1);
    }
    
    const occurrences = new Set();
    for (const [key, value] of count) {
        if (occurrences.has(value)) {
            return false;
        }
        occurrences.add(value);
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组一次统计频次，然后遍历频次集合检查唯一性，总体为O(n)
空间复杂度O(n)最坏情况下哈希表存储n个不同元素，集合也可能存储n个不同的频次