2024-11-30：质数的最大距离。用 go 语言，给定一个整数数组 nums，请找出两个（可以是相同的）质数在该数组中的下标之间的最大距离。提示： nums 的长度在 [1,3*10^5] 之间。 num

作者：福大大架构师每日一题

2024-11-30
北京
本文字数：1242 字
阅读完需：约 4 分钟

2024-11-30：质数的最大距离。用 go 语言，给定一个整数数组 nums，请找出两个（可以是相同的）质数在该数组中的下标之间的最大距离。

提示：

nums 的长度在[1,3*10^5]之间。

nums 的每个元素的值在[1,100]。

输入保证 nums 中至少有一个质数。

输入： nums = [4,2,9,5,3]。

输出： 3。

解释： nums[1]、nums[3] 和 nums[4] 是质数。因此答案是 |4 - 1| = 3。

答案 2024-11-30：

chatgpt

题目来自 leetcode3115。

大体步骤如下：

1.定义一个函数 maximumPrimeDifference(nums []int) int 用于计算质数的最大距离。其中，根据给定的质数列表 primes 和数组 nums：

创建一个 map primeSet 用于存储质数的出现情况。
遍历 nums 数组，找到第一个质数的下标，并记录在变量 first 中。
再次遍历 nums 数组，找到最后一个质数的下标，并记录在变量 last 中。
返回最后一个质数的下标与第一个质数的下标之间的距离。

2.在主函数 main 中，定义一个示例数组 nums := []int{4, 2, 9, 5, 3}。

3.调用 maximumPrimeDifference(nums) 函数，并输出结果。

总体时间复杂度为 O(n), 其中 n 为数组 nums 的长度。

总体空间复杂度为 O(1)，并不随输入规模变化。

Go 完整代码如下：

package main
import (  "fmt")
func maximumPrimeDifference(nums []int) int {  primes := []int{2, 3, 5, 7, 11,    13, 17, 19, 23, 29,    31, 37, 41, 43, 47,    53, 59, 61, 67, 71,    73, 79, 83, 89, 97}  primeSet := make(map[int]struct{})  for _, v := range primes {    primeSet[v] = struct{}{}  }  n := len(nums)  first := 0  for i := 0; i < n; i++ {    if _, ok := primeSet[nums[i]]; ok {      first = i      break    }  }  last := 0  for i := n - 1; i >= 0; i-- {    if _, ok := primeSet[nums[i]]; ok {      last = i      break    }  }  return last - first}
func main() {  nums := []int{4, 2, 9, 5, 3}  fmt.Println(maximumPrimeDifference(nums))}

复制代码

Rust 完整代码如下：

fn maximum_prime_difference(nums: Vec<i32>) -> i32 {    let primes = [        2, 3, 5, 7, 11, 13, 17, 19, 23, 29,        31, 37, 41, 43, 47, 53, 59, 61, 67,        71, 73, 79, 83, 89, 97,    ];
    let prime_set: std::collections::HashSet<i32> = primes.iter().cloned().collect();    let n = nums.len();        let mut first = -1;    for i in 0..n {        if prime_set.contains(&nums[i]) {            first = i as i32;            break;        }    }
    let mut last = -1;    for i in (0..n).rev() {        if prime_set.contains(&nums[i]) {            last = i as i32;            break;        }    }
    if first == -1 || last == -1 {         return 0; // 如果不存在质数    }
    last - first}
fn main() {    let nums = vec![4, 2, 9, 5, 3];    println!("{}", maximum_prime_difference(nums));}