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

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[1]

题目来自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

}

}

returnlast- first

}

func main(){

nums :=[]int{4,2,9,5,3}

fmt.Println(maximumPrimeDifference(nums))

}

在这里插入图片描述Rust完整代码如下：

fn maximum_prime_difference(nums:Vec<i32>)->i32{

letprimes=[

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,

];

letprime_set: std::collections::HashSet<i32>= primes.iter().cloned().collect();

letn= nums.len();

letmut first=-1;

foriin0..n {

if prime_set.contains(&nums[i]){

first = i asi32;

break;

}

}

letmut last=-1;

foriin(0..n).rev(){

if prime_set.contains(&nums[i]){

last = i asi32;

break;

}

}

if first ==-1|| last ==-1{

return0;// 如果不存在质数

}

last - first

}

fnmain(){

letnums=vec![4,2,9,5,3];

println!("{}",maximum_prime_difference(nums));

}

在这里插入图片描述引用链接