Every day a Leetcode

题目来源：3044. 出现频率最高的质数

解法1：哈希

对于每个单元格，枚举 8 个方向，生成数字，用一个哈希表统计其中质数个数。

最后返回出现次数最多的质数，如果有多个这样的质数，返回最大的那个。

代码：

/** @lc app=leetcode.cn id=3044 lang=cpp** [3044] 出现频率最高的质数*/// @lc code=start
class Solution
{
private:const int dx[8] = {-1, -1, -1, 1, 1, 1, 0, 0};const int dy[8] = {0, -1, 1, 0, -1, 1, -1, 1};public:int mostFrequentPrime(vector<vector<int>> &mat){if (mat.empty())return 0;int m = mat.size(), n = m ? mat[0].size() : 0;unordered_map<int, int> cnt;for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)for (int k = 0; k < 8; k++){int r = i + dx[k], c = j + dy[k], v = mat[i][j];// 只统计大于 10 的质数// if (isPrime(v))//     cnt[v]++;while (r >= 0 && r < m && c >= 0 && c < n){v = 10 * v + mat[r][c];if (isPrime(v))cnt[v]++;r += dx[k];c += dy[k];}}int ans = -1, maxCount = 0;for (auto &[num, count] : cnt){if (count > maxCount){ans = num;maxCount = count;}else if (count == maxCount)ans = max(ans, num);}return ans;}// 辅函数 - 判断数字 n 是否是质数bool isPrime(int n){for (int i = 2; i * i <= n; i++){if (n % i == 0)return false;}return true;}
};
// @lc code=end

结果：

复杂度分析：

时间复杂度：O(mnk*10^k/2)，其中 m 和 n 分别为 mat 的行数和列数，k=max(m,n)。总共有 O(mnk) 个数，判断质数需要 O(10^k/2) 的时间。

空间复杂度：O(mnk)，其中 m 和 n 分别为 mat 的行数和列数，k=max(m,n)。