出现频率最高的质数

难度: Medium

给你一个大小为 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

Submission

运行时间: 87 ms

内存: 16.0 MB

class Solution:
    def mostFrequentPrime(self, mat: List[List[int]]) -> int:
        dire=[(i,j) for i in range(-1,2) for j in range(-1,2) if not i==j==0]
        def chkPrime(a):
            if a<10 or a%2==0:
                return False
            for i in range(3,int(a**0.5)+1,2):
                if a%i==0:
                    return False
            return True
        d=defaultdict(int)
        row,col=len(mat),len(mat[0])
        for y0 in range(row):
            for x0 in range(col):
                for dy,dx in dire:
                    y,x=y0,x0
                    a=mat[y][x]
                    while 1:
                        y+=dy
                        x+=dx
                        if not (0<=y<row and 0<=x<col):
                            break
                        a=a*10+mat[y][x]
                        if chkPrime(a):
                            d[a]+=1
        l=sorted(d.items(),key=lambda x:(-x[1],-x[0]))
        return l[0][0] if l else -1

Explain

这个题解首先定义了所有可能的移动方向，即8个方向（东、东南、南等）。然后，使用一个辅助函数chkPrime来检查一个数字是否是大于10的质数。对于矩阵中的每个元素，它尝试所有8个方向，并沿着每个方向生成新的数字，使用累加的方式将当前数字附加在已有数字之后。如果生成的数字是一个质数，则在字典d中记录该数字的出现次数。最后，将字典中的项目按出现次数降序排序，如果有相同频次的质数，则按数值降序排序，返回出现频率最高的质数。如果没有找到任何符合条件的质数，则返回-1。

时间复杂度: O(m*n*(m+n)*sqrt(a))

空间复杂度: O(m*n*(m+n))

# 最高频质数查找器
class Solution:
    def mostFrequentPrime(self, mat: List[List[int]]) -> int:
        # 定义8个可能的移动方向
dire=[(i,j) for i in range(-1,2) for j in range(-1,2) if not i==j==0]
        # 检查大于10的质数
        def chkPrime(a):
            if a<10 or a%2==0:
                return False
            for i in range(3,int(a**0.5)+1,2):
                if a%i==0:
                    return False
            return True
        # 记录每个质数的出现频率
        d=defaultdict(int)
        row,col=len(mat),len(mat[0])
        for y0 in range(row):
            for x0 in range(col):
                for dy,dx in dire:
                    y,x=y0,x0
                    a=mat[y][x]
                    # 沿着某方向生成数字
                    while 1:
                        y+=dy
                        x+=dx
                        if not (0<=y<row and 0<=x<col):
                            break
                        a=a*10+mat[y][x]
                        if chkPrime(a):
                            d[a]+=1
        # 排序并返回出现最频繁的质数
        l=sorted(d.items(),key=lambda x:(-x[1],-x[0]))
        return l[0][0] if l else -1

Explore

在移动过程中生成数字时，每次移动前都会检查新的坐标(y, x)是否仍然在矩阵的边界内（即0<=y<row和0<=x<col）。如果这些条件不成立，即意味着新坐标越界了，那么循环会中断，这个方向的数字生成也就停止了。这样可以确保所有生成的数字都是由矩阵内部的有效元素构成，不会因为索引越界而引入不存在的矩阵元素。

在该题解中，需要找到的是大于10的质数，所以直接排除所有小于10的数字可以减少不必要的质数检查，提高效率。同时，除了2以外的所有偶数都不是质数，因此排除偶数也是为了减少不必要的质数检验，从而优化算法的性能。排除这些明显不符合条件的数字，可以让程序集中处理更可能是质数的数字，有效提高算法的执行效率。

使用`not i==j==0`是为了排除(0, 0)这个方向，因为(0, 0)代表的是原位置，即不移动。在这个题目中，我们需要在矩阵中沿着不同方向生成新的数字，如果包括(0, 0)方向，就会导致在原地重复使用同一个数字，这并不符合题目要求生成新数字的目的。因此，排除这个方向是必须的，以保证所有的方向都是向外移动的。