2614.对角线上的质数:遍历(质数判断)

【LetMeFly】2614.对角线上的质数:遍历(质数判断)

力扣题目链接:https://leetcode.cn/problems/prime-in-diagonal/

给你一个下标从 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]

 

示例 1:

输入:nums = [[1,2,3],[5,6,7],[9,10,11]]
输出:11
解释:数字 1、3、6、9 和 11 是所有 "位于至少一条对角线上" 的数字。由于 11 是最大的质数,故返回 11 。

示例 2:

输入:nums = [[1,2,3],[5,17,7],[9,11,10]]
输出:17
解释:数字 1、3、9、10 和 17 是所有满足"位于至少一条对角线上"的数字。由于 17 是最大的质数,故返回 17 。

 

提示:

  • 1 <= nums.length <= 300
  • nums.length == numsi.length
  • 1 <= nums[i][j] <= 4*106

解题方法:质数判断

如何判断一个数是否为质数?

首先如果这个数小于2那么一定不是质数

用$i$从2到$sqrt(n)$枚举,若$i$能整除$n$,则$n$不是质数

否则$n$是质数

如何遍历对角线?题目中说了 nums.length == numsi.length ,也就是说矩阵是正方形。

所以我们可以用$i$从$0$枚举到$n - 1$,那么$nums[i][i]$和$nums[i][len(nums) - i - 1]$即为对角线和副对角线上的元素。

  • 时间复杂度$O(len(nums)\sqrt{\max(nums[i][j]))}$
  • 空间复杂度$O(1)$

AC代码

C++

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
29
30
31
32
33
34
/*
* @Author: LetMeFly
* @Date: 2025-03-18 23:40:09
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-03-18 23:43:36
*/
class Solution {
private:
bool isPrime(int n) {
if (n < 2) {
return false;
}
int k = sqrt(n);
for (int i = 2; i <= k; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
public:
int diagonalPrime(vector<vector<int>>& nums) {
int ans = 0;
for (int i = 0; i < nums.size(); i++) {
if (isPrime(nums[i][i])) {
ans = max(ans, nums[i][i]);
}
if (isPrime(nums[i][nums.size() - i - 1])) {
ans = max(ans, nums[i][nums.size() - i - 1]);
}
}
return ans;
}
};

Python

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
'''
Author: LetMeFly
Date: 2025-03-18 23:46:52
LastEditors: LetMeFly.xyz
LastEditTime: 2025-03-18 23:48:14
'''
from typing import List
from math import sqrt

class Solution:
def isPrime(self, n: int) -> bool:
if n < 2:
return False
for i in range(2, int(sqrt(n)) + 1):
if n % i == 0:
return False
return True

def diagonalPrime(self, nums: List[List[int]]) -> int:
ans = 0
for i in range(len(nums)):
if self.isPrime(nums[i][i]):
ans = max(ans, nums[i][i])
if self.isPrime(nums[i][len(nums) - i - 1]):
ans = max(ans, nums[i][len(nums) - i - 1])
return ans

Java

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
29
30
31
32
33
/*
* @Author: LetMeFly
* @Date: 2025-03-18 23:50:23
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-03-18 23:55:24
*/
class Solution {
private boolean isPrime(int n) {
if (n < 2) {
return false;
}
int k = (int)Math.sqrt(n);
for (int i = 2; i <= k; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}

public int diagonalPrime(int[][] nums) {
int ans = 0;
for (int i = 0; i < nums.length; i++) {
if (isPrime(nums[i][i])) {
ans = Math.max(ans, nums[i][i]);
}
if (isPrime(nums[i][nums.length - i - 1])) {
ans = Math.max(ans, nums[i][nums.length - i - 1]);
}
}
return ans;
}
}

Go

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
29
30
31
/*
* @Author: LetMeFly
* @Date: 2025-03-18 23:55:55
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-03-18 23:58:46
*/
package main

func isPrime2614(n int) (ans bool) {
if n < 2 {
return
}
for i := 2; i * i <= n; i++ {
if n % i == 0 {
return
}
}
return true
}

func diagonalPrime(nums [][]int) (ans int) {
for i := range nums {
if isPrime2614(nums[i][i]) {
ans = max(ans, nums[i][i])
}
if isPrime2614(nums[i][len(nums) - i - 1]) {
ans = max(ans, nums[i][len(nums) - i - 1])
}
}
return
}

同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~

千篇源码题解已开源


2614.对角线上的质数:遍历(质数判断)
https://blog.letmefly.xyz/2025/03/18/LeetCode 2614.对角线上的质数/
作者
发布于
2025年3月18日
许可协议