LeetCode 题解工作台
对角线上的质数
给你一个下标从 0 开始的二维整数数组 nums 。 返回位于 nums 至少一条 对角线 上的最大 质数 。如果任一对角线上均不存在质数，返回 0 。 注意： 如果某个整数大于 1 ，且不存在除 1 和自身之外的正整数因子，则认为该整数是一个质数。 如果存在整数 i ，使得 nums[i][i] …
4
题型
7
代码语言
3
相关题
当前训练重点
简单 · 数组·数学
答案摘要
我们实现一个函数 `is_prime`，判断一个数是否为质数。 然后遍历数组，判断对角线上的数是否为质数，如果是，更新答案。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·数学 题型思路
题目描述
给你一个下标从 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 <= 300nums.length == numsi.length1 <= nums[i][j] <= 4*106
解题思路
方法一：数学 + 模拟
我们实现一个函数 is_prime，判断一个数是否为质数。
然后遍历数组，判断对角线上的数是否为质数，如果是，更新答案。
时间复杂度 ，其中 和 分别为数组的行数和数组中的最大值。空间复杂度 。
class Solution:
def diagonalPrime(self, nums: List[List[int]]) -> int:
def is_prime(x: int) -> bool:
if x < 2:
return False
return all(x % i for i in range(2, int(sqrt(x)) + 1))
n = len(nums)
ans = 0
for i, row in enumerate(nums):
if is_prime(row[i]):
ans = max(ans, row[i])
if is_prime(row[n - i - 1]):
ans = max(ans, row[n - i - 1])
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n * sqrt(m)) where n is the matrix size and m is the maximum element, due to checking primality for each diagonal element. Space complexity is O(n) for storing diagonal numbers temporarily. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect candidates to iterate only over diagonals rather than the full matrix.
- question_mark
Look for optimized primality checks rather than naive looping over all numbers.
- question_mark
Notice if candidates handle the edge case where no prime exists.
常见陷阱
外企场景- error
Iterating over the entire matrix instead of just the diagonals wastes time.
- error
Checking primality inefficiently can lead to timeouts for large numbers.
- error
Failing to return 0 when no prime exists on the diagonals.
进阶变体
外企场景- arrow_right_alt
Find the smallest prime on any diagonal instead of the largest.
- arrow_right_alt
Sum all prime numbers on the diagonals rather than returning the maximum.
- arrow_right_alt
Check only the main diagonal for primes and ignore the anti-diagonal.