【矩阵】【方向】【素数】3044 出现频率最高的素数

本文涉及知识点

素数 矩阵 方向

LeetCode 3044 出现频率最高的素数

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

分析

四层循环：第一层枚举起始行，第二层循环枚举起始列，第三层循环枚举方向。第三层循环：

一，num = mat[r][c]。

二，移动d格后是否越界，如果越界退出第四层循环，否则num = num*10+mat[nr][nc]。

三，所有num 如果是大于10的质数，则mNumCount[num]++。

四，找出频率最大的素数，如果有多个，返回值最大的。

时间复杂度：O(nmmax(n,m)8)。

初始化的时候：枚举所有[2,1⁶]的质数。

代码

核心代码

class Solution {
public:
  int mostFrequentPrime(vector<vector<int>>& mat) {
    static const auto& v = CreatePrime(1000'000);
    static unordered_set<int> setPrime;
    if (setPrime.empty())
    {
      for (auto& n : v)
      {
        if (n > 10)
        {
          setPrime.emplace(n);
        }
      }
    }
    int move[8][2] = { {0,1},{0,-1},{1,0},{-1,0},{1,1},{-1,-1},{1,-1},{-1,1} };
    unordered_map<int, int> mNumCount;
    for (int r = 0; r < mat.size(); r++)
    {
      for (int c = 0; c < mat[0].size(); c++)
      {
        for (int d = 0; d < sizeof(move) / sizeof(move[0]); d++)
        {
          int num = mat[r][c];
          for (int k = 1;; k++)
          {
            const int nr = r + move[d][0] * k;
            const int nc = c + move[d][1] * k;
            if ((nr < 0) || (nr >= mat.size()))
            {
              break;
            }
            if ((nc < 0) || (nc >= mat[0].size()))
            {
              break;
            }
            num = num * 10 + mat[nr][nc];
            if (setPrime.count(num))
            {
              mNumCount[num]++;
            }
          }
        }
      }
    }
    vector<pair<int, int>> vCntNum;
    for (const auto& [num, cnt] : mNumCount)
    {
      vCntNum.emplace_back(cnt, num);
    }
    sort(vCntNum.begin(), vCntNum.end());
    return vCntNum.size() ? vCntNum.rbegin()->second : -1;
  }
};

template<class T,class T2>
void Assert(const T& t1, const T2& t2)
{
assert(t1 == t2);
}
template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}
int main()
{
vector<vector> mat;
{
Solution sln;
mat = { {1,1},{9,9},{1,1} };
auto res = sln.mostFrequentPrime(mat);
Assert(19, res);
}
{
Solution sln;
mat = { {7} };
auto res = sln.mostFrequentPrime(mat);
Assert(-1, res);
}
{
Solution sln;
mat = { {9,7,8} ,{4,6,5},{2,8,6} };
auto res = sln.mostFrequentPrime(mat);
Assert(97, res);
}
}

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者 操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。