Medium

题目描述

给你一个整数数组 nums。

返回 nums 中第一个（从左到右扫描）频率唯一的元素。也就是说，没有其他整数在 nums 中出现相同的次数。如果没有这样的元素，返回 -1。

示例 1：

输入：nums = [20,10,30,30]
输出：30
解释：
20 出现 1 次。
10 出现 1 次。
30 出现 2 次。
30 的频率是唯一的，因为没有其他整数恰好出现 2 次。

示例 2：

输入：nums = [20,20,10,30,30,30]
输出：20
解释：
20 出现 2 次。
10 出现 1 次。
30 出现 3 次。
20、10 和 30 的频率都是唯一的。第一个具有唯一频率的元素是 20。

示例 3：

输入：nums = [10,10,20,20]
输出：-1
解释：
10 出现 2 次。
20 出现 2 次。
没有元素具有唯一频率。

约束条件：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5

解题思路

这道题需要找到第一个频率唯一的元素，可以分解为两个步骤：

基本思路：

  1. 统计频率：遍历数组，统计每个元素的出现次数
  2. 统计频率的频率：统计每个频率值出现了多少次，判断哪些频率是唯一的
  3. 找第一个元素：再次从左到右遍历数组，找到第一个频率唯一的元素

具体实现：

  • 使用哈希表 freq 记录每个元素的出现频率
  • 使用哈希表 freqCount 记录每个频率值的出现次数
  • 最后遍历原数组，对于每个元素，检查其频率是否唯一（即 freqCount[freq[x]] == 1）

时间复杂度优化： 虽然需要三次遍历，但每次遍历都是 O(n)，总体时间复杂度仍为 O(n)。空间复杂度为 O(n)，用于存储两个哈希表。

这种解法思路清晰，易于理解和实现，是处理频率统计问题的经典模式。

代码实现

class Solution {
public:
    int firstUniqueFreq(vector<int>& nums) {
        unordered_map<int, int> freq;
        unordered_map<int, int> freqCount;
        
        // 统计每个元素的频率
        for (int num : nums) {
            freq[num]++;
        }
        
        // 统计每个频率的出现次数
        for (auto& p : freq) {
            freqCount[p.second]++;
        }
        
        // 从左到右找第一个频率唯一的元素
        for (int num : nums) {
            if (freqCount[freq[num]] == 1) {
                return num;
            }
        }
        
        return -1;
    }
};

class Solution:
    def firstUniqueFreq(self, nums: List[int]) -> int:
        freq = {}
        freq_count = {}
        
        # 统计每个元素的频率
        for num in nums:
            freq[num] = freq.get(num, 0) + 1
        
        # 统计每个频率的出现次数
        for f in freq.values():
            freq_count[f] = freq_count.get(f, 0) + 1
        
        # 从左到右找第一个频率唯一的元素
        for num in nums:
            if freq_count[freq[num]] == 1:
                return num
        
        return -1

public class Solution {
    public int FirstUniqueFreq(int[] nums) {
        Dictionary<int, int> freq = new Dictionary<int, int>();
        Dictionary<int, int> freqCount = new Dictionary<int, int>();
        
        // 统计每个元素的频率
        foreach (int num in nums) {
            freq[num] = freq.GetValueOrDefault(num, 0) + 1;
        }
        
        // 统计每个频率的出现次数
        foreach (var f in freq.Values) {
            freqCount[f] = freqCount.GetValueOrDefault(f, 0) + 1;
        }
        
        // 从左到右找第一个频率唯一的元素
        foreach (int num in nums) {
            if (freqCount[freq[num]] == 1) {
                return num;
            }
        }
        
        return -1;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var firstUniqueFreq = function(nums) {
    const freq = new Map();
    for (const num of nums) {
        freq.set(num, (freq.get(num) || 0) + 1);
    }
    
    const freqCount = new Map();
    for (const count of freq.values()) {
        freqCount.set(count, (freqCount.get(count) || 0) + 1);
    }
    
    for (const num of nums) {
        if (freqCount.get(freq.get(num)) === 1) {
            return num;
        }
    }
    
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要三次遍历数组，每次遍历都是 O(n)
空间复杂度O(n)需要两个哈希表存储元素频率和频率统计