对角线上的质数

难度: Easy

给你一个下标从 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 == nums_i.length
1 <= nums[i][j] <= 4*10⁶

Submission

运行时间: 32 ms

内存: 27.4 MB

class Solution:
    def diagonalPrime(self, nums: List[List[int]]) -> int:
        def is_prime(n):
            if n == 1:
                return False
            if n <= 3:
                return True
            if n % 2 == 0:
                return False
            if n % 3 == 0:
                return False
            for i in range(3,int(n**0.5)+1,2):
                if n % i == 0:
                    return False
            return True
        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

Explain

该题解采用了直接遍历矩阵的两条对角线上的元素，并检查每个元素是否为质数的方法。遍历过程中，如果发现一个质数且比当前记录的最大质数大，则更新最大质数的记录。为了高效检查一个数是否为质数，题解中使用了一个辅助函数is_prime，该函数首先排除了一些特殊情况（如小于等于3的数和偶数），然后利用试除法检查是否有非1和自身的因子。

时间复杂度: O(n * sqrt(n))

空间复杂度: O(1)

class Solution:
    def diagonalPrime(self, nums: List[List[int]]) -> int:
        def is_prime(n):
            if n == 1:
                return False
            if n <= 3:
                return True
            if n % 2 == 0:
                return False
            if n % 3 == 0:
                return False
            for i in range(3,int(n**0.5)+1,2):
                if n % i == 0:
                    return False
            return True
        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

Explore

在题解中，并没有明确提及对空数组或非常小的数组的特殊处理逻辑。为了确保程序对这些情况正确处理，应当在函数开始处添加检查，例如，首先检查数组是否为空，如果是，则应当返回一个默认值，如0或特定错误信息。此外，也应检查数组的尺寸是否足够大，以至于能包含至少一条对角线。若数组尺寸过小，同样应返回默认值或错误信息。

如果数组只有一行或一列，题解中的程序会将这唯一的行或列视为对角线上的元素。在这种情况下，程序会正确地遍历这些元素并检查它们是否为质数。因此，这不会影响结果的正确性，只是对角线的概念在这种情况下与通常的多行多列的情况略有不同。

在试除法中从3开始并每次增加2的原因是为了避免检查偶数，因为除了2之外的所有偶数都不是质数。通过从3开始并只检查奇数（即每次增加2），可以提高检查效率，减少不必要的除法操作。这是一种常用的优化方法，尤其适用于大数的质数检测。

程序通过遍历数组的行，并在每行中分别检查对应索引的元素（主对角线）和对称索引的元素（副对角线）来确保只检查两条对角线。具体来说，对于主对角线，它检查位置为 `(i, i)` 的元素，对于副对角线，它检查位置为 `(i, len(row)-1-i)` 的元素。这种方法确保了即使在数组具有多行多列的情况下，也只会检查位于这两条对角线上的元素。