2025-12-05：檢查元素頻次是否為質數。用go語言，給定一個整數數組 nums，判斷數組中是否存在某個數，它在數組中出現的次數是質數。若至少有一個元素的出現次數為質數則返回 true，否則返回 false。説明：質數指大於1且只有1和自身兩個正因數的整數。
1 <= nums.length <= 100。
0 <= nums[i] <= 100。
輸入： nums = [1,2,3,4,5,4]。
輸出： true。
解釋：
數字 4 的頻次是 2，而 2 是質數。
題目來自力扣3591。
自然智慧即可。
📝 步驟詳解
-
統計元素頻率 程序首先創建一個空的映射（map）
cnt，用於記錄每個整數在數組nums中出現的次數。接着，遍歷整個nums數組。對於數組中的每一個元素x，都在映射cnt中將其對應的計數值加 1。遍歷結束後，映射cnt中就存儲了每個不同數字在數組中出現的頻次 。 -
檢查頻次是否為質數 獲得頻率統計後，程序開始遍歷映射
cnt中的所有值，即每個數字的出現頻次c。對於每一個頻次c，程序使用 Go 標準庫math/big中的ProbablyPrime(0)方法來判斷其是否為質數 。這個方法對質數的判斷是確定性的（當入參為 0 時），能夠準確判斷c是否是質數。 -
返回判斷結果 在遍歷頻次的過程中，只要發現任何一個頻次
c被確認為質數，函數會立即返回true，表示數組中存在出現次數為質數的元素。如果遍歷完所有的頻次後，都沒有發現質數頻次，函數則返回false。
⏱️ 複雜度分析
-
總的時間複雜度：**O(N + K * M)**。
N是數組nums的長度。第一步統計頻率需要遍歷整個數組，時間複雜度為 O(N)。K是數組中不同數字的個數（即映射cnt的大小）。在最壞情況下，所有數字都不同，K等於N。M是判斷一個最大為N的數是否為質數所需的時間複雜度。ProbablyPrime(0)方法對於N的最大值 100 來説是非常高效的。- 因此，總體時間複雜度是線性的 O(N)。
-
總的額外空間複雜度：**O(N)**。
- 主要的空間開銷來自於存儲頻率統計的映射
cnt。在最壞情況下（所有元素都不同），該映射需要存儲N個鍵值對，因此空間複雜度為 O(N) 。
- 主要的空間開銷來自於存儲頻率統計的映射
Go完整代碼如下：
package main
import (
"fmt"
"math/big"
)
func checkPrimeFrequency(nums []int) bool {
cnt := map[int]int{}
for _, x := range nums {
cnt[x]++
}
for _, c := range cnt {
if big.NewInt(int64(c)).ProbablyPrime(0) {
return true
}
}
return false
}
func main() {
nums := []int{1, 2, 3, 4, 5, 4}
result := checkPrimeFrequency(nums)
fmt.Println(result)
}
Python完整代碼如下：
# -*-coding:utf-8-*-
from collections import Counter
import sympy
def check_prime_frequency(nums):
"""
檢查數組中是否有數字的出現頻率是質數
參數:
nums: 整數列表
返回:
bool: 如果存在出現頻率為質數的數字則返回True，否則返回False
"""
# 統計每個數字出現的頻率
freq = Counter(nums)
# 檢查每個頻率值是否為質數
for count in freq.values():
# 使用sympy的isprime函數檢查質數
# 注意：sympy.isprime對小於2的數返回False
if sympy.isprime(count):
return True
return False
# 測試樣例
if __name__ == "__main__":
nums = [1, 2, 3, 4, 5, 4]
result = check_prime_frequency(nums)
print(result) # 輸出: True
# 更多測試用例
test_cases = [
[1, 1, 2, 2, 3], # 頻率: 1(2次), 2(2次), 3(1次) - 質數頻率2
[1, 1, 1], # 頻率: 1(3次) - 質數頻率3
[1, 2, 3], # 頻率: 1(1次), 2(1次), 3(1次) - 沒有質數頻率
[], # 空數組 - 沒有質數頻率
[5, 5, 5, 5], # 頻率: 5(4次) - 4不是質數
]
for i, test in enumerate(test_cases, 1):
print(f"測試用例{i}: {test} -> {check_prime_frequency(test)}")
C++完整代碼如下：
#include <iostream>
#include <unordered_map>
#include <vector>
#include <cmath>
// 判斷一個數是否為質數
bool isPrime(int n) {
if (n <= 1) return false; // 1及以下的數不是質數
if (n <= 3) return true; // 2和3是質數
if (n % 2 == 0 || n % 3 == 0) return false; // 能被2或3整除的不是質數
// 檢查6k±1形式的因子
for (int i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) {
return false;
}
}
return true;
}
// 檢查數組中是否有數字的出現頻率是質數
bool checkPrimeFrequency(const std::vector<int>& nums) {
// 使用哈希表統計每個數字的出現頻率
std::unordered_map<int, int> frequency;
// 統計頻率
for (int num : nums) {
frequency[num]++;
}
// 檢查每個頻率值是否為質數
for (const auto& pair : frequency) {
if (isPrime(pair.second)) {
return true;
}
}
return false;
}
int main() {
// 測試用例
std::vector<int> nums = {1, 2, 3, 4, 5, 4};
// 調用函數並輸出結果
bool result = checkPrimeFrequency(nums);
std::cout << result << std::endl; // 輸出: true
// 更多測試用例
std::vector<std::vector<int>> testCases = {
{1, 1, 2, 2, 3}, // 頻率: 1(2次), 2(2次), 3(1次) - 質數頻率2
{1, 1, 1}, // 頻率: 1(3次) - 質數頻率3
{1, 2, 3}, // 頻率: 1(1次), 2(1次), 3(1次) - 沒有質數頻率
{}, // 空數組 - 沒有質數頻率
{5, 5, 5, 5}, // 頻率: 5(4次) - 4不是質數
{7, 7, 7, 7, 7, 7, 7}, // 頻率: 7(7次) - 7是質數
};
std::cout << "\n更多測試用例：" << std::endl;
for (size_t i = 0; i < testCases.size(); ++i) {
std::cout << "測試用例 " << i + 1 << ": ";
for (int num : testCases[i]) {
std::cout << num << " ";
}
std::cout << "-> " << checkPrimeFrequency(testCases[i]) << std::endl;
}
return 0;
}
