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：
题目来自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));
}
