对角线上的质数

难度:

标签:

题目描述

You are given a 0-indexed two-dimensional integer array nums.

Return the largest prime number that lies on at least one of the diagonals of nums. In case, no prime is present on any of the diagonals, return 0.

Note that:

An integer is prime if it is greater than 1 and has no positive integer divisors other than 1 and itself.
An integer val is on one of the diagonals of nums if there exists an integer i for which nums[i][i] = val or an i for which nums[i][nums.length - i - 1] = val.

In the above diagram, one diagonal is [1,5,9] and another diagonal is [3,5,7].

Example 1:

Input: nums = [[1,2,3],[5,6,7],[9,10,11]]
Output: 11
Explanation: The numbers 1, 3, 6, 9, and 11 are the only numbers present on at least one of the diagonals. Since 11 is the largest prime, we return 11.

Example 2:

Input: nums = [[1,2,3],[5,17,7],[9,11,10]]
Output: 17
Explanation: The numbers 1, 3, 9, 10, and 17 are all present on at least one of the diagonals. 17 is the largest prime, so we return 17.

Constraints:

1 <= nums.length <= 300
nums.length == nums_i.length
1 <= nums[i][j] <= 4*10⁶

代码结果

运行时间: 32 ms, 内存: 27.4 MB

/* 
题目思路：
1. 使用Java Stream遍历二维数组的对角线元素，包括主对角线和副对角线。
2. 过滤出质数并找到最大的质数。
*/
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class Solution {
    public int diagonalPrime(int[][] nums) {
        int n = nums.length;
        return Stream.concat(
                    IntStream.range(0, n).map(i -> nums[i][i]).boxed(),
                    IntStream.range(0, n).map(i -> nums[i][n - i - 1]).boxed()
                )
                .filter(this::isPrime)
                .max(Integer::compare)
                .orElse(0);
    }

    // 辅助方法：判断一个数是否为质数
    private boolean isPrime(int num) {
        if (num <= 1) return false;
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) return false;
        }
        return true;
    }
}

解释

方法:

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

时间复杂度:

O(n * sqrt(n))

空间复杂度:

O(1)

代码细节讲解

🦆

如何确保此题解中的程序对稀异情况（如空的或超小的数组）的处理正确？

▷

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

🦆

如果数组仅有一行或一列，程序将如何处理？这会影响结果的正确性吗？

▷

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

🦆

在使用试除法检查质数时，为什么选择从3开始并每次增加2进行检查？

▷

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

🦆

如果数组中有超过两行或两列，程序如何确保只检查两条对角线？

▷

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

对角线上的质数

题目描述

代码结果

解释

代码细节讲解

相关问题