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^6

解题思路

这道题要求我们找到矩阵两条对角线上的最大质数。

解题思路：

  1. 提取对角线元素：矩阵有两条对角线

    • 主对角线：从左上到右下，坐标为 (i, i)
    • 副对角线：从右上到左下，坐标为 (i, n-1-i)

  2. 质数判断：对每个对角线元素判断是否为质数

    • 质数必须大于1
    • 只需检查到 √n 即可，如果在此范围内没有因子，则为质数

  3. 找最大值：遍历所有对角线元素，记录最大的质数

算法步骤：

  1. 遍历矩阵的对角线位置
  2. 对每个对角线元素调用质数判断函数
  3. 维护当前找到的最大质数
  4. 返回结果（如果没有找到质数则返回0）

优化点：

  • 使用集合去重，避免重复检查中心元素（当矩阵大小为奇数时，两条对角线会在中心相交）
  • 质数判断使用 O(√n) 算法

代码实现

class Solution {
public:
    bool isPrime(int n) {
        if (n <= 1) return false;
        if (n <= 3) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;
        
        for (int i = 5; i * i <= n; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }
    
    int diagonalPrime(vector<vector<int>>& nums) {
        int n = nums.size();
        unordered_set<int> diagonalElements;
        
        // 收集对角线元素
        for (int i = 0; i < n; i++) {
            diagonalElements.insert(nums[i][i]); // 主对角线
            diagonalElements.insert(nums[i][n - 1 - i]); // 副对角线
        }
        
        int maxPrime = 0;
        for (int num : diagonalElements) {
            if (isPrime(num)) {
                maxPrime = max(maxPrime, num);
            }
        }
        
        return maxPrime;
    }
};

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 or n % 3 == 0:
                return False
            
            i = 5
            while i * i <= n:
                if n % i == 0 or n % (i + 2) == 0:
                    return False
                i += 6
            return True
        
        n = len(nums)
        diagonal_elements = set()
        
        # 收集对角线元素
        for i in range(n):
            diagonal_elements.add(nums[i][i])  # 主对角线
            diagonal_elements.add(nums[i][n - 1 - i])  # 副对角线
        
        max_prime = 0
        for num in diagonal_elements:
            if is_prime(num):
                max_prime = max(max_prime, num)
        
        return max_prime

public class Solution {
    private bool IsPrime(int n) {
        if (n <= 1) return false;
        if (n <= 3) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;
        
        for (int i = 5; i * i <= n; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }
    
    public int DiagonalPrime(int[][] nums) {
        int n = nums.Length;
        HashSet<int> diagonalElements = new HashSet<int>();
        
        // 收集对角线元素
        for (int i = 0; i < n; i++) {
            diagonalElements.Add(nums[i][i]); // 主对角线
            diagonalElements.Add(nums[i][n - 1 - i]); // 副对角线
        }
        
        int maxPrime = 0;
        foreach (int num in diagonalElements) {
            if (IsPrime(num)) {
                maxPrime = Math.Max(maxPrime, num);
            }
        }
        
        return maxPrime;
    }
}

var diagonalPrime = function(nums) {
    function isPrime(n) {
        if (n <= 1) return false;
        if (n <= 3) return true;
        if (n % 2 === 0 || n % 3 === 0) return false;
        for (let i = 5; i * i <= n; i += 6) {
            if (n % i === 0 || n % (i + 2) === 0) return false;
        }
        return true;
    }
    
    let maxPrime = 0;
    let n = nums.length;
    
    for (let i = 0; i < n; i++) {
        if (isPrime(nums[i][i])) {
            maxPrime = Math.max(maxPrime, nums[i][i]);
        }
        if (isPrime(nums[i][n - 1 - i])) {
            maxPrime = Math.max(maxPrime, nums[i][n - 1 - i]);
        }
    }
    
    return maxPrime;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n + k√m)n为矩阵大小，k为不同对角线元素个数(最多2n)，m为最大元素值
空间复杂度O(n)存储对角线元素的哈希集合