出现频率最高的质数

You are given a m x n 0-indexed 2D matrix mat. From every cell, you can create numbers in the following way:

• There could be at most 8 paths from the cells namely: east, south-east, south, south-west, west, north-west, north, and north-east.
• Select a path from them and append digits in this path to the number being formed by traveling in this direction.
• Note that numbers are generated at every step, for example, if the digits along the path are 1, 9, 1, then there will be three numbers generated along the way: 1, 19, 191.

Return the most frequent prime number greater than 10 out of all the numbers created by traversing the matrix or -1 if no such prime number exists. If there are multiple prime numbers with the highest frequency, then return the largest among them.

Note: It is invalid to change the direction during the move.

 

Example 1:

Input: mat = [[1,1],[9,9],[1,1]]
Output: 19
Explanation: 
From cell (0,0) there are 3 possible directions and the numbers greater than 10 which can be created in those directions are:
East: [11], South-East: [19], South: [19,191].
Numbers greater than 10 created from the cell (0,1) in all possible directions are: [19,191,19,11].
Numbers greater than 10 created from the cell (1,0) in all possible directions are: [99,91,91,91,91].
Numbers greater than 10 created from the cell (1,1) in all possible directions are: [91,91,99,91,91].
Numbers greater than 10 created from the cell (2,0) in all possible directions are: [11,19,191,19].
Numbers greater than 10 created from the cell (2,1) in all possible directions are: [11,19,19,191].
The most frequent prime number among all the created numbers is 19.

Example 2:

Input: mat = [[7]]
Output: -1
Explanation: The only number which can be formed is 7. It is a prime number however it is not greater than 10, so return -1.

Example 3:

Input: mat = [[9,7,8],[4,6,5],[2,8,6]]
Output: 97
Explanation: 
Numbers greater than 10 created from the cell (0,0) in all possible directions are: [97,978,96,966,94,942].
Numbers greater than 10 created from the cell (0,1) in all possible directions are: [78,75,76,768,74,79].
Numbers greater than 10 created from the cell (0,2) in all possible directions are: [85,856,86,862,87,879].
Numbers greater than 10 created from the cell (1,0) in all possible directions are: [46,465,48,42,49,47].
Numbers greater than 10 created from the cell (1,1) in all possible directions are: [65,66,68,62,64,69,67,68].
Numbers greater than 10 created from the cell (1,2) in all possible directions are: [56,58,56,564,57,58].
Numbers greater than 10 created from the cell (2,0) in all possible directions are: [28,286,24,249,26,268].
Numbers greater than 10 created from the cell (2,1) in all possible directions are: [86,82,84,86,867,85].
Numbers greater than 10 created from the cell (2,2) in all possible directions are: [68,682,66,669,65,658].
The most frequent prime number among all the created numbers is 97.

 

Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 6
• 1 <= mat[i][j] <= 9

/*
题目思路：
1. 定义一个方法用于判断一个数是否是质数。
2. 使用流式操作生成每个单元格的所有可能的路径数字。
3. 使用流操作统计所有大于 10 的质数的频率，找到出现频率最高的质数。
*/
import java.util.*;
import java.util.stream.*;

public class Solution {
    private boolean isPrime(int num) {
        if (num <= 1) return false;
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) return false;
        }
        return true;
    }

    public int mostFrequentPrime(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[][] directions = {{0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}};

        Map<Integer, Long> primeCountMap = IntStream.range(0, m)
            .boxed()
            .flatMap(i -> IntStream.range(0, n)
                .boxed()
                .flatMap(j -> Arrays.stream(directions)
                    .map(dir -> {
                        List<Integer> numbers = new ArrayList<>();
                        int x = i, y = j, num = 0;
                        while (x >= 0 && x < m && y >= 0 && y < n) {
                            num = num * 10 + mat[x][y];
                            numbers.add(num);
                            x += dir[0];
                            y += dir[1];
                        }
                        return numbers.stream();
                    })
                    .flatMap(s -> s)
                    .filter(n -> n > 10 && isPrime(n))))
            .collect(Collectors.groupingBy(n -> n, Collectors.counting()));

        return primeCountMap.entrySet().stream()
            .max(Map.Entry.<Integer, Long>comparingByValue()
                .thenComparing(Map.Entry.comparingByKey()))
            .map(Map.Entry::getKey)
            .orElse(-1);
    }
}

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

O(m*n*(m+n)*sqrt(a))

O(m*n*(m+n))