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

福大大架构师每日一题

发布于 2024-12-03 21:12:53

27900

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

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));
}