Medium

题目描述

给你一个整数数组 nums。

返回数组中两个（不一定不同）质数下标之间的最大距离。

示例 1：

输入：nums = [4,2,9,5,3]
输出：3
解释：nums[1]、nums[3] 和 nums[4] 是质数。所以答案是 |4 - 1| = 3。

示例 2：

输入：nums = [4,8,2,8]
输出：0
解释：nums[2] 是质数。因为只有一个质数，所以答案是 |2 - 2| = 0。

提示：

  • 1 <= nums.length <= 3 * 10^5
  • 1 <= nums[i] <= 100
  • 输入保证数组中至少有一个质数

提示：

  • 找出 nums 中的所有质数
  • 找出 nums 中第一个和最后一个质数

解题思路

解题思路

这道题要求找到数组中两个质数下标之间的最大距离。我们可以分析一下：

核心观察：要使两个质数下标之间的距离最大，显然应该选择最左边的质数和最右边的质数。

解法分析：

  1. 暴力枚举法：遍历所有质数对，计算距离的最大值。时间复杂度 O(n²)，对于大数据会超时。

  2. 双指针优化法（推荐）：由于我们只需要最大距离，实际上只需要找到第一个质数位置和最后一个质数位置即可。

    • 从左往右找第一个质数位置 first
    • 从右往左找最后一个质数位置 last
    • 返回 last - first

质数判断：由于数组元素范围是 1-100，我们可以预处理所有100以内的质数，或者写一个简单的质数判断函数。

实现细节：

  • 质数定义：大于1且只能被1和自身整除的自然数
  • 特殊情况：如果只有一个质数，距离为0
  • 可以使用Set存储质数以提高查找效率

时间复杂度：O(n)，空间复杂度：O(1)

代码实现

class Solution {
public:
    bool isPrime(int n) {
        if (n < 2) return false;
        if (n == 2) return true;
        if (n % 2 == 0) return false;
        for (int i = 3; i * i <= n; i += 2) {
            if (n % i == 0) return false;
        }
        return true;
    }
    
    int maximumPrimeDifference(vector<int>& nums) {
        int first = -1, last = -1;
        
        for (int i = 0; i < nums.size(); i++) {
            if (isPrime(nums[i])) {
                if (first == -1) first = i;
                last = i;
            }
        }
        
        return last - first;
    }
};

class Solution:
    def maximumPrimeDifference(self, nums: List[int]) -> int:
        def is_prime(n):
            if n < 2:
                return False
            if n == 2:
                return True
            if n % 2 == 0:
                return False
            for i in range(3, int(n**0.5) + 1, 2):
                if n % i == 0:
                    return False
            return True
        
        first, last = -1, -1
        
        for i in range(len(nums)):
            if is_prime(nums[i]):
                if first == -1:
                    first = i
                last = i
        
        return last - first

public class Solution {
    private bool IsPrime(int n) {
        if (n < 2) return false;
        if (n == 2) return true;
        if (n % 2 == 0) return false;
        for (int i = 3; i * i <= n; i += 2) {
            if (n % i == 0) return false;
        }
        return true;
    }
    
    public int MaximumPrimeDifference(int[] nums) {
        int first = -1, last = -1;
        
        for (int i = 0; i < nums.Length; i++) {
            if (IsPrime(nums[i])) {
                if (first == -1) first = i;
                last = i;
            }
        }
        
        return last - first;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumPrimeDifference = function(nums) {
    const isPrime = (n) => {
        if (n < 2) return false;
        if (n === 2) return true;
        if (n % 2 === 0) return false;
        for (let i = 3; i * i <= n; i += 2) {
            if (n % i === 0) return false;
        }
        return true;
    };
    
    let first = -1, last = -1;
    
    for (let i = 0; i < nums.length; i++) {
        if (isPrime(nums[i])) {
            if (first === -1) first = i;
            last = i;
        }
    }
    
    return last - first;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)遍历数组一次，质数判断为常数时间（元素范围1-100）
空间复杂度O(1)只使用常数额外空间