Medium
题目描述
给你一个 m x n 的二维矩阵 mat，矩阵下标从 0 开始。从每个单元格出发，你可以按以下方式创建数字：
- 最多可以从单元格出发沿 8 个方向移动：东、东南、南、西南、西、西北、北、东北。
- 从这些方向中选择一个路径，并将沿着这个方向移动时经过的数字追加到正在形成的数字中。
- 注意数字在每一步都会生成，例如，如果路径上的数字是 1, 9, 1，那么沿途会生成三个数字：1, 19, 191。
返回遍历矩阵创建的所有数字中大于 10 的最频繁的质数，如果不存在这样的质数则返回 -1。如果有多个质数具有最高频率，则返回其中最大的那个。
注意： 移动过程中不能改变方向。
示例 1：
输入：mat = [[1,1],[9,9],[1,1]]
输出：19
示例 2：
输入：mat = [[7]]
输出：-1
解释：唯一能形成的数字是 7。它是质数但不大于 10，所以返回 -1。
示例 3：
输入：mat = [[9,7,8],[4,6,5],[2,8,6]]
输出：97
提示：
m == mat.lengthn == mat[i].length1 <= m, n <= 61 <= mat[i][j] <= 9
解题思路
这道题需要我们从矩阵的每个位置出发，沿着8个方向生成所有可能的数字，然后统计大于10的质数的频率。
核心思路：
方向枚举： 定义8个方向的偏移量：东、东南、南、西南、西、西北、北、东北。
数字生成： 从每个单元格出发，沿每个方向递归生成数字。每走一步都会形成一个新数字，需要检查是否大于10且为质数。
质数判断： 实现一个高效的质数判断函数，由于矩阵最大6x6，生成的数字不会太大。
频率统计： 使用哈希表记录每个质数出现的次数，最后找出频率最高且数值最大的质数。
算法流程：
- 遍历矩阵每个位置作为起点
- 对每个起点，尝试8个方向
- 在每个方向上递归前进，生成所有可能的数字
- 对每个大于10的数字判断是否为质数并统计频率
- 返回频率最高的最大质数
由于矩阵规模较小（最大6x6），可以使用暴力枚举的方法。
代码实现
class Solution {
public:
int mostFrequentPrime(vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
unordered_map<int, int> freq;
// 8个方向：东、东南、南、西南、西、西北、北、东北
vector<pair<int, int>> dirs = {{0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1}, {-1,0}, {-1,1}};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
for (auto& dir : dirs) {
generateNumbers(mat, i, j, dir.first, dir.second, 0, freq);
}
}
}
int result = -1;
int maxFreq = 0;
for (auto& p : freq) {
if (p.second > maxFreq || (p.second == maxFreq && p.first > result)) {
maxFreq = p.second;
result = p.first;
}
}
return result;
}
private:
void generateNumbers(vector<vector<int>>& mat, int x, int y, int dx, int dy, int num, unordered_map<int, int>& freq) {
if (x < 0 || x >= mat.size() || y < 0 || y >= mat[0].size()) {
return;
}
num = num * 10 + mat[x][y];
if (num > 10 && isPrime(num)) {
freq[num]++;
}
generateNumbers(mat, x + dx, y + dy, dx, dy, num, freq);
}
bool isPrime(int n) {
if (n < 2) return false;
if (n == 2) return true;
if (n % 2 == 0) return false;
for (int i = 3; i * i <= n; i += 2) {
if (n % i == 0) return false;
}
return true;
}
};
class Solution:
def mostFrequentPrime(self, mat: List[List[int]]) -> int:
m, n = len(mat), len(mat[0])
freq = {}
# 8个方向：东、东南、南、西南、西、西北、北、东北
directions = [(0,1), (1,1), (1,0), (1,-1), (0,-1), (-1,-1), (-1,0), (-1,1)]
def is_prime(num):
if num < 2:
return False
if num == 2:
return True
if num % 2 == 0:
return False
i = 3
while i * i <= num:
if num % i == 0:
return False
i += 2
return True
def generate_numbers(x, y, dx, dy, num):
if x < 0 or x >= m or y < 0 or y >= n:
return
num = num * 10 + mat[x][y]
if num > 10 and is_prime(num):
freq[num] = freq.get(num, 0) + 1
generate_numbers(x + dx, y + dy, dx, dy, num)
for i in range(m):
for j in range(n):
for dx, dy in directions:
generate_numbers(i, j, dx, dy, 0)
if not freq:
return -1
max_freq = max(freq.values())
result = max(num for num, f in freq.items() if f == max_freq)
return result
public class Solution {
public int MostFrequentPrime(int[][] mat) {
int m = mat.Length, n = mat[0].Length;
Dictionary<int, int> freq = new Dictionary<int, int>();
// 8个方向：东、东南、南、西南、西、西北、北、东北
int[,] dirs = {{0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1}, {-1,0}, {-1,1}};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
for (int d = 0; d < 8; d++) {
GenerateNumbers(mat, i, j, dirs[d,0], dirs[d,1], 0, freq);
}
}
}
int result = -1;
int maxFreq = 0;
foreach (var kvp in freq) {
if (kvp.Value > maxFreq || (kvp.Value == maxFreq && kvp.Key > result)) {
maxFreq = kvp.Value;
result = kvp.Key;
}
}
return result;
}
private void GenerateNumbers(int[][] mat, int x, int y, int dx, int dy, int num, Dictionary<int, int> freq) {
if (x < 0 || x >= mat.Length || y < 0 || y >= mat[0].Length) {
return;
}
num = num * 10 + mat[x][y];
if (num > 10 && IsPrime(num)) {
freq[num] = freq.GetValueOrDefault(num, 0) + 1;
}
GenerateNumbers(mat, x + dx, y + dy, dx, dy, num, freq);
}
private bool IsPrime(int n) {
if (n < 2) return false;
if (n == 2) return true;
if (n % 2 == 0) return false;
for (int i = 3; i * i <= n; i += 2) {
if (n % i == 0) return false;
}
return true;
}
}
var mostFrequentPrime = function(mat) {
const m = mat.length;
const n = mat[0].length;
const directions = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];
const freq = new Map();
function isPrime(num) {
if (num < 2) return false;
if (num === 2) return true;
if (num % 2 === 0) return false;
for (let i = 3; i * i <= num; i += 2) {
if (num % i === 0) return false;
}
return true;
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
for (let [di, dj] of directions) {
let num = 0;
let x = i, y = j;
while (x >= 0 && x < m && y >= 0 && y < n) {
num = num * 10 + mat[x][y];
if (num > 10 && isPrime(num)) {
freq.set(num, (freq.get(num) || 0) + 1);
}
x += di;
y += dj;
}
}
}
}
if (freq.size === 0) return -1;
let maxFreq = 0;
let result = -1;
for (let [prime, count] of freq) {
if (count > maxFreq || (count === maxFreq && prime > result)) {
maxFreq = count;
result = prime;
}
}
return result;
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(m × n × 8 × max_length × √max_num)，其中 max_length 是最长路径长度，max_num 是生成的最大数字 |
| 空间复杂度 | O(number_of_unique_primes + recursion_depth) |