题目描述
给你一个大小为 m x n
、下标从 0 开始的二维矩阵 mat
。在每个单元格,你可以按以下方式生成数字:
- 最多有
8
条路径可以选择:东,东南,南,西南,西,西北,北,东北。 - 选择其中一条路径,沿着这个方向移动,并且将路径上的数字添加到正在形成的数字后面。
- 注意,每一步都会生成数字,例如,如果路径上的数字是 1, 9, 1,那么在这个方向上会生成三个数字:1, 19, 191 。
返回在遍历矩阵所创建的所有数字中,出现频率最高的、大于 10
的素数;如果不存在这样的素数,则返回 -1
。如果存在多个出现频率最高的素数,那么返回其中最大的那个。
注意:移动过程中不允许改变方向。
样例
输入:mat = [[1,1],[9,9],[1,1]]
输出:19
解释:
从单元格 (0,0) 出发,有 3 个可能的方向,这些方向上可以生成的大于 10 的数字有:
东方向: [11], 东南方向: [19], 南方向: [19,191]。
从单元格 (0,1) 出发,所有可能方向上生成的大于 10 的数字有:[19,191,19,11]。
从单元格 (1,0) 出发,所有可能方向上生成的大于 10 的数字有:[99,91,91,91,91]。
从单元格 (1,1) 出发,所有可能方向上生成的大于 10 的数字有:[91,91,99,91,91]。
从单元格 (2,0) 出发,所有可能方向上生成的大于 10 的数字有:[11,19,191,19]。
从单元格 (2,1) 出发,所有可能方向上生成的大于 10 的数字有:[11,19,19,191]。
在所有生成的数字中,出现频率最高的素数是 19。
输入:mat = [[7]]
输出:-1
解释:唯一可以生成的数字是 7。它是一个素数,但不大于 10,所以返回 -1。
输入:mat = [[9,7,8],[4,6,5],[2,8,6]]
输出:97
解释:
从单元格 (0,0) 出发,所有可能方向上生成的大于 10 的数字有:[97,978,96,966,94,942]。
从单元格 (0,1) 出发,所有可能方向上生成的大于 10 的数字有:[78,75,76,768,74,79]。
从单元格 (0,2) 出发,所有可能方向上生成的大于 10 的数字有:[85,856,86,862,87,879]。
从单元格 (1,0) 出发,所有可能方向上生成的大于 10 的数字有:[46,465,48,42,49,47]。
从单元格 (1,1) 出发,所有可能方向上生成的大于 10 的数字有:[65,66,68,62,64,69,67,68]。
从单元格 (1,2) 出发,所有可能方向上生成的大于 10 的数字有:[56,58,56,564,57,58]。
从单元格 (2,0) 出发,所有可能方向上生成的大于 10 的数字有:[28,286,24,249,26,268]。
从单元格 (2,1) 出发,所有可能方向上生成的大于 10 的数字有:[86,82,84,86,867,85]。
从单元格 (2,2) 出发,所有可能方向上生成的大于 10 的数字有:[68,682,66,669,65,658]。
在所有生成的数字中,出现频率最高的素数是 97。
限制
m == mat.length
n == mat[i].length
1 <= m, n <= 6
1 <= mat[i][j] <= 9
算法
(暴力枚举) $O(mn(m + n) (10^{\frac{m}{2}} + 10^{\frac{n}{2}}))$
- 暴力枚举每个单元格,然后统计出这个单元格上八个方向所有路径上的数字,并注意判定是否为素数。
时间复杂度
- 每个单元格需要遍历 $O(m + n)$ 次,且每次遍历需要 $O(10^{\frac{m}{2}})$ 或 $O(10^{\frac{n}{2}})$ 的时间判定。
- 故总时间复杂度为 $O(mn(m + n) (10^{\frac{m}{2}} + 10^{\frac{n}{2}}))$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
private:
bool valid(int x) {
if (x < 10)
return false;
for (int i = 2; i * i <= x; i++)
if (x % i == 0)
return false;
return true;
}
public:
int mostFrequentPrime(vector<vector<int>>& mat) {
const int m = mat.size(), n = mat[0].size();
const int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
unordered_map<int, int> seen;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
for (int d = 0; d < 8; d++) {
int num = 0, x = i, y = j;
while (x >= 0 && x < m && y >= 0 && y < n) {
num = num * 10 + mat[x][y];
if (valid(num))
++seen[num];
x += dx[d]; y += dy[d];
}
}
int ans = -1, tot = 0;
for (const auto &[k, v] : seen)
if (tot < v) {
tot = v;
ans = k;
} else if (tot == v) {
ans = max(ans, k);
}
return ans;
}
};