题目描述
给你一个下标从 0 开始的二维整数数组 nums
。
返回位于 nums
至少一条 对角线 上的最大 质数。如果任一对角线上均不存在质数,返回 0
。
注意:
- 如果某个整数大于
1
,且不存在除1
和自身之外的正整数因子,则认为该整数是一个质数。 - 如果存在整数
i
,使得nums[i][i] = val
或者nums[i][nums.length - i - 1] = val
,则认为整数val
位于nums
的一条对角线上。
在上图中,一条对角线是 [1,5,9],而另一条对角线是 [3,5,7]。
样例
输入:nums = [[1,2,3],[5,6,7],[9,10,11]]
输出:11
解释:数字 1、3、6、9 和 11 是所有 "位于至少一条对角线上" 的数字。由于 11 是最大的质数,故返回 11。
输入:nums = [[1,2,3],[5,17,7],[9,11,10]]
输出:17
解释:数字 1、3、9、10 和 17 是所有满足"位于至少一条对角线上"的数字。由于 17 是最大的质数,故返回 17。
限制
1 <= nums.length <= 300
nums.length == nums_i.length
1 <= nums[i][j] <= 4*10^6
算法
(模拟) $O(n \sqrt m)$
- 遍历两个对角线的数字,逐一判断是否为质数。
时间复杂度
- 每个数字 $m$ 需要 $O(\sqrt m)$ 的时间判断,故时间复杂度为 $O(n \sqrt m)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
private:
bool is_prime(int x) {
if (x <= 1)
return false;
for (int i = 2; i * i <= x; i++)
if (x % i == 0)
return false;
return true;
}
public:
int diagonalPrime(vector<vector<int>>& nums) {
const int n = nums.size();
int ans = 0;
for (int i = 0; i < n; i++) {
if (is_prime(nums[i][i]))
ans = max(ans, nums[i][i]);
if (is_prime(nums[i][n - i - 1]))
ans = max(ans, nums[i][n - i - 1]);
}
return ans;
}
};