3591. 检查元素频次是否为质数

题目描述

给你一个整数数组 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

解法

方法一：计数 + 判断质数

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

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

Python3JavaC++GoTypeScript

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())

import java.util.*;

class Solution {
    public boolean checkPrimeFrequency(int[] nums) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : nums) {
            cnt.merge(x, 1, Integer::sum);
        }

        for (int x : cnt.values()) {
            if (isPrime(x)) {
                return true;
            }
        }
        return false;
    }

    private boolean isPrime(int x) {
        if (x < 2) {
            return false;
        }
        for (int i = 2; i <= x / i; i++) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }
}

class Solution {
public:
    bool checkPrimeFrequency(vector<int>& nums) {
        unordered_map<int, int> cnt;
        for (int x : nums) {
            ++cnt[x];
        }

        for (auto& [_, x] : cnt) {
            if (isPrime(x)) {
                return true;
            }
        }
        return false;
    }

private:
    bool isPrime(int x) {
        if (x < 2) {
            return false;
        }
        for (int i = 2; i <= x / i; ++i) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }
};

func checkPrimeFrequency(nums []int) bool {
    cnt := make(map[int]int)
    for _, x := range nums {
        cnt[x]++
    }
    for _, x := range cnt {
        if isPrime(x) {
            return true
        }
    }
    return false
}

func isPrime(x int) bool {
    if x < 2 {
        return false
    }
    for i := 2; i*i <= x; i++ {
        if x%i == 0 {
            return false
        }
    }
    return true
}

function checkPrimeFrequency(nums: number[]): boolean {
    const cnt: Record<number, number> = {};
    for (const x of nums) {
        cnt[x] = (cnt[x] || 0) + 1;
    }
    for (const x of Object.values(cnt)) {
        if (isPrime(x)) {
            return true;
        }
    }
    return false;
}

function isPrime(x: number): boolean {
    if (x < 2) {
        return false;
    }
    for (let i = 2; i * i <= x; i++) {
        if (x % i === 0) {
            return false;
        }
    }
    return true;
}

3591. 检查元素频次是否为质数

题目描述

解法

方法一：计数 + 判断质数

评论