How do I check if a number is prime?

You can check if a number is prime by verifying that it is greater than 1 and not divisible by any number other than 1 and itself. An efficient way to check is by testing divisibility up to the square root of the number.

How can I optimize the prime checking part of this problem?

You can optimize by checking divisibility only up to the square root of the number, and skipping even numbers greater than 2, as they are not prime.

What if there is no element with a prime frequency?

If no element has a prime frequency, the solution should return false, as there are no frequencies that are prime.

How does the array size impact the solution?

The array size affects the time complexity, especially in counting frequencies, but the maximum size of 100 ensures the approach will run efficiently within the problem's constraints.

Why is the prime checking function necessary?

The prime checking function is essential for determining if any of the element frequencies are prime, which is the core requirement of the problem.

#3591

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

检查元素频次是否为质数

给你一个整数数组 nums 。如果数组中任一元素的频次是质数，返回 true ；否则，返回 false 。元素 x 的频次是它在数组中出现的次数。质数是一个大于 1 的自然数，并且只有两个因数：1 和它本身。示例 1：输入： nums = [1,2,3,4,5,4] 输出： t…

数组哈希表数学计数数论

题目描述

给你一个整数数组 nums。

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

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

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

示例 1：

输入： nums = [1,2,3,4,5,4]

输出： true

解释：

数字 4 的频次是 2，而 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

lightbulb

解题思路

方法一：计数 + 判断质数

我们用一个哈希表 $\text{cnt}$ 统计每个元素的频次。然后遍历 $\text{cnt}$ 中的值，判断是否有质数，如果有则返回 true，否则返回 false。

时间复杂度 $O(n \times \sqrt{M})$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 $\text{nums}$ 的长度，而 $M$ 是 $\text{cnt}$ 中的最大值。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def checkPrimeFrequency(self, nums: List[int]) -> bool:
        def is_prime(x: int) -> bool:
            if x < 2:
                return False
            return all(x % i for i in range(2, int(sqrt(x)) + 1))

        cnt = Counter(nums)
        return any(is_prime(x) for x in cnt.values())

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate identifies the prime checking pattern and efficiently counts frequencies.
question_mark
Candidate demonstrates knowledge of basic number theory to optimize the primality check.
question_mark
Candidate implements a clear and correct array scanning strategy with hash table lookups.

warning

常见陷阱

外企场景

error
Not implementing an efficient prime checking function leading to slower performance.
error
Incorrectly counting frequencies or misunderstanding the concept of frequency.
error
Failing to handle edge cases such as small arrays or the case where no element has a prime frequency.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the array contains repeated zeros?
arrow_right_alt
What if the array has a length of 1?
arrow_right_alt
How does the solution change if the array contains a larger range of numbers?

help

常见问题

外企场景

继续练习

#3312 查询排序后的最大公约数 #3044 出现频率最高的质数 #2748 美丽下标对的数目