What is the most efficient approach for the Most Frequent Prime problem?

Use recursion to explore numbers from each cell and a hash map to track frequencies of primes over 10, then select the most frequent.

How do I handle ties in the Most Frequent Prime problem?

Compare all primes with the highest frequency and return the largest prime among them.

Can numbers smaller than 10 be considered primes here?

No, only primes strictly greater than 10 are considered valid for this problem.

Does changing direction in the matrix affect the result?

Yes, changing direction is invalid. Numbers must be formed by moving straight in one direction from the starting cell.

Is hash map usage necessary for Most Frequent Prime?

While not strictly required, a hash map efficiently tracks the frequency of generated numbers and identifies the most frequent prime.

#3044

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

出现频率最高的质数

给你一个大小为 m x n 、下标从 0 开始的二维矩阵 mat 。在每个单元格，你可以按以下方式生成数字：最多有 8 条路径可以选择：东，东南，南，西南，西，西北，北，东北。选择其中一条路径，沿着这个方向移动，并且将路径上的数字添加到正在形成的数字后面。注意，每一步都会生成数字，例如，如果路…

数组哈希表数学矩阵计数

题目描述

给你一个大小为 m x n 、下标从 0 开始的二维矩阵 mat 。在每个单元格，你可以按以下方式生成数字：

最多有 8 条路径可以选择：东，东南，南，西南，西，西北，北，东北。
选择其中一条路径，沿着这个方向移动，并且将路径上的数字添加到正在形成的数字后面。
注意，每一步都会生成数字，例如，如果路径上的数字是 1, 9, 1，那么在这个方向上会生成三个数字：1, 19, 191 。

返回在遍历矩阵所创建的所有数字中，出现频率最高的、大于 10的质数；如果不存在这样的质数，则返回 -1 。如果存在多个出现频率最高的质数，那么返回其中最大的那个。

注意：移动过程中不允许改变方向。

示例 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 。

示例 2：

输入：mat = [[7]]
输出：-1
解释：唯一可以生成的数字是 7 。它是一个质数，但不大于 10 ，所以返回 -1 。

示例 3：

输入：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

lightbulb

解题思路

方法一：哈希表 + 枚举

我们可以使用哈希表来统计每个大于 10 的素数出现的次数。

对于每个单元格，我们可以从它出发，沿着 8 个方向之一生成数字，然后判断生成的数字是否是大于 $10$ 的素数，如果是的话，就将它加入到哈希表中。

最后，我们遍历哈希表，找到出现频率最高的质数，如果有多个出现频率最高的质数，那么返回其中最大的那个。

时间复杂度 $O(m \times n \times \max(m, n) \times {10}^{\frac{\max(m, n)}{2}})$ ，空间复杂度 $O(m \times n \times \max(m, n))$ 。其中 $m$ 和 $n$ 分别是 mat 的行数和列数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

class Solution:
    def mostFrequentPrime(self, mat: List[List[int]]) -> int:
        def is_prime(x: int) -> int:
            return all(x % i != 0 for i in range(2, isqrt(x) + 1))

        m, n = len(mat), len(mat[0])
        cnt = Counter()
        for i in range(m):
            for j in range(n):
                for a in range(-1, 2):
                    for b in range(-1, 2):
                        if a == 0 and b == 0:
                            continue
                        x, y, v = i + a, j + b, mat[i][j]
                        while 0 <= x < m and 0 <= y < n:
                            v = v * 10 + mat[x][y]
                            if is_prime(v):
                                cnt[v] += 1
                            x, y = x + a, y + b
        ans, mx = -1, 0
        for v, x in cnt.items():
            if mx < x:
                mx = x
                ans = v
            elif mx == x:
                ans = max(ans, v)
        return ans

speed

复杂度分析

指标	值
时间	complexity depends on the number of cells m _n and the maximum number length generated from each cell, roughly O(m_ n*maxLen). Space complexity is dominated by the hash map storing generated numbers, O(uniqueNumbers).
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Checks if you can efficiently explore all paths from each cell using recursion.
question_mark
Observes if you can apply a hash map to track number frequencies correctly.
question_mark
Tests your ability to combine number theory with array scanning patterns.

warning

常见陷阱

外企场景

error
Failing to stop recursion when moving out of matrix bounds.
error
Counting non-prime numbers or primes less than or equal to 10.
error
Incorrectly choosing between tied primes without selecting the largest.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the smallest most frequent prime instead of the largest when ties occur.
arrow_right_alt
Allow numbers formed by moving in any direction, including diagonals, changing directions mid-path.
arrow_right_alt
Count frequencies for all numbers, not just primes, to find the most common number in the matrix.

help

常见问题

外企场景

继续练习

#3312 查询排序后的最大公约数 #2748 美丽下标对的数目 #3591 检查元素频次是否为质数