Easy

题目描述

给定一个整数数组 nums。

如果数组中任何元素的频率是质数，则返回 true，否则返回 false。

元素 x 的频率是它在数组中出现的次数。

质数是大于 1 且只有 1 和它本身两个因数的自然数。

示例 1：

输入：nums = [1,2,3,4,5,4]
输出：true
解释：
4 的频率为 2，这是一个质数。

示例 2：

输入：nums = [1,2,3,4,5]
输出：false
解释：
所有元素的频率都是 1。

示例 3：

输入：nums = [2,2,2,4,4]
输出：true
解释：
2 和 4 的频率都是质数。

约束条件：

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 100

解题思路

解题思路

这道题需要我们完成两个主要步骤：

1. 统计元素频率

使用哈希表统计数组中每个元素的出现次数。对于给定的约束条件，数组长度最多为100，因此频率最大值也不超过100。

2. 判断质数

实现一个辅助函数来判断一个数是否为质数。质数的定义是大于1且只有1和它本身两个因数的自然数。对于小范围的数字，可以使用试除法：从2开始到√n，检查是否有能整除n的数。

3. 检查频率

遍历所有统计得到的频率值，如果发现任何一个频率是质数，就返回true。如果所有频率都不是质数，则返回false。

算法优化点：

  • 由于数组长度限制，频率值较小，质数判断的时间复杂度可以忽略
  • 可以预计算小范围内的质数来优化，但对于此题规模来说不是必需的

推荐解法： 哈希表统计频率 + 试除法判断质数，简单直观且效率足够。

代码实现

class Solution {
public:
    bool checkPrimeFrequency(vector<int>& nums) {
        unordered_map<int, int> freq;
        for (int num : nums) {
            freq[num]++;
        }
        
        for (auto& pair : freq) {
            if (isPrime(pair.second)) {
                return true;
            }
        }
        
        return false;
    }
    
private:
    bool isPrime(int n) {
        if (n <= 1) return false;
        if (n <= 3) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;
        
        for (int i = 5; i * i <= n; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) {
                return false;
            }
        }
        
        return true;
    }
};

class Solution:
    def checkPrimeFrequency(self, nums: List[int]) -> bool:
        from collections import Counter
        
        freq = Counter(nums)
        
        for count in freq.values():
            if self.isPrime(count):
                return True
        
        return False
    
    def isPrime(self, n):
        if n <= 1:
            return False
        if n <= 3:
            return True
        if n % 2 == 0 or n % 3 == 0:
            return False
        
        i = 5
        while i * i <= n:
            if n % i == 0 or n % (i + 2) == 0:
                return False
            i += 6
        
        return True

public class Solution {
    public bool CheckPrimeFrequency(int[] nums) {
        Dictionary<int, int> freq = new Dictionary<int, int>();
        
        foreach (int num in nums) {
            freq[num] = freq.GetValueOrDefault(num, 0) + 1;
        }
        
        foreach (var count in freq.Values) {
            if (IsPrime(count)) {
                return true;
            }
        }
        
        return false;
    }
    
    private bool IsPrime(int n) {
        if (n <= 1) return false;
        if (n <= 3) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;
        
        for (int i = 5; i * i <= n; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) {
                return false;
            }
        }
        
        return true;
    }
}

var checkPrimeFrequency = function(nums) {
    const isPrime = (n) => {
        if (n < 2) return false;
        for (let i = 2; i <= Math.sqrt(n); i++) {
            if (n % i === 0) return false;
        }
        return true;
    };
    
    const freq = {};
    for (const num of nums) {
        freq[num] = (freq[num] || 0) + 1;
    }
    
    return Object.values(freq).some(isPrime);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n + k√f)n为数组长度，k为不同元素个数，f为最大频率值
空间复杂度O(k)k为不同元素个数，用于存储频率统计