2614-对角线上的质数

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:27 2023-09-13 16:06:27 Updated    

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

本题视频讲解

如何高效地判断一个数是否为质数？见【周赛 340】 。

思路

遍历两条对角线上的元素，如果是质数则更新答案的最大值。

注意 1 不是质数。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def is_prime(n: int) -> bool:
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return n >= 2  # 1 不是质数

class Solution:
    def diagonalPrime(self, nums: List[List[int]]) -> int:
        ans = 0
        for i, row in enumerate(nums):
            for x in row[i], row[-1 - i]:
                if x > ans and is_prime(x):
                    ans = x
        return ans
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int diagonalPrime(int[][] nums) {
        int n = nums.length, ans = 0;
        for (int i = 0; i < n; ++i) {
            int x = nums[i][i];
            if (x > ans && isPrime(x))
                ans = x;
            x = nums[i][n - 1 - i];
            if (x > ans && isPrime(x))
                ans = x;
        }
        return ans;
    }

    private boolean isPrime(int n) {
        for (int i = 2; i * i <= n; ++i)
            if (n % i == 0)
                return false;
        return n >= 2; // 1 不是质数
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    bool is_prime(int n) {
        for (int i = 2; i * i <= n; ++i)
            if (n % i == 0)
                return false;
        return n >= 2; // 1 不是质数
    }

public:
    int diagonalPrime(vector<vector<int>> &nums) {
        int n = nums.size(), ans = 0;
        for (int i = 0; i < n; ++i) {
            if (int x = nums[i][i]; x > ans && is_prime(x))
                ans = x;
            if (int x = nums[i][n - 1 - i]; x > ans && is_prime(x))
                ans = x;
        }
        return ans;
    }
};
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func isPrime(n int) bool {
	for i := 2; i*i <= n; i++ {
		if n%i == 0 {
			return false
		}
	}
	return n >= 2 // 1 不是质数
}

func diagonalPrime(nums [][]int) (ans int) {
	for i, row := range nums {
		if x := row[i]; x > ans && isPrime(x) {
			ans = x
		}
		if x := row[len(nums)-1-i]; x > ans && isPrime(x) {
			ans = x
		}
	}
	return
}

复杂度分析

  • 时间复杂度：O(n\sqrt{U})，其中 n 为 nums 的长度，U 为两条对角线上的最大值。
  • 空间复杂度：O(1)。仅用到若干额外变量。
 Comments
On this page
2614-对角线上的质数
  1. 本题视频讲解
  2. 思路
  3. 复杂度分析