【力扣 - 每日一题】3115. 质数的最大距离（一次遍历、头尾遍历、空间换时间、埃式筛、欧拉筛、打表）Golang实现

原题链接

题目描述

给你一个整数数组 nums。
返回两个（不一定不同的）质数在 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\ast 10^5$
$1<=nums[i]<=100$
输入保证 nums 中至少有一个质数。

思路1：一次遍历

函数checkIsPrime用于判断num是否为质数，时间复杂度为$O(sqrt(n))$
一次遍历，维护minPos表示最小的质数位置，maxPos表示最大的质数位置，最后maxPos-minPos就是答案
维护的时候，如果该数是质数，更新maxPos；如果minPos未被更新过，即minPos为初始值-1，更新minPos

整体时间复杂度$O(N\ast sqrt(M))$
代码如下：

func checkIsPrime(num int) bool {if num <= 1 {return false}for i := 2; i*i <= num; i ++ {if num % i == 0 {return false}}return true
}
func maximumPrimeDifference(nums []int) int {minPos,maxPos := -1,-1for idx,elem := range nums {if checkIsPrime(elem) {if minPos == -1 {minPos = idx}maxPos = idx}}return maxPos - minPos
}

思路2：分别从头尾遍历

在思路1的基础上考虑对maxPos的更新过程进行优化，含义为最大的质数出现的位置，所以倒序遍历找第一个质数即可。
极端情况下，最中间的数是质数，还是会把全部的数都判断一遍。

代码：

func checkIsPrime(num int) bool {if num <= 1 {return false}for i := 2; i*i <= num; i ++ {if num % i == 0 {return false}}return true
}
func maximumPrimeDifference(nums []int) int {minPos,maxPos := -1,-1for idx,elem := range nums {if checkIsPrime(elem) {minPos = idxbreak}}for idx := len(nums) - 1; idx >= 0; idx -- {if checkIsPrime(nums[idx]) {maxPos = idx break}}return maxPos - minPos
}

思路3：标记结果 空间换时间

在思路1的基础上，考虑有的数如果重复出现的话，会被重复判断。
额外开辟map，存储该数是否为素数，空间换时间。
代码如下：

func checkIsPrime(num int) bool {if num <= 1 {return false}for i := 2; i*i <= num; i ++ {if num % i == 0 {return false}}return true
}
func maximumPrimeDifference(nums []int) int {minPos,maxPos := -1,-1mp := make(map[int]bool,len(nums))for idx,elem := range nums {if flag,ok := mp[elem]; ok {if flag {if minPos == -1 {minPos = idx}maxPos = idx}continue}if checkIsPrime(elem) {if minPos == -1 {minPos = idx}maxPos = idxmp[elem] = true}else{mp[elem] = false}}return maxPos - minPos
}

实际上并没有优化时间，很奇怪

思路4：埃式筛

可以考虑使用素数筛预处理得到所有质数，其中埃式筛的时间复杂度是$O(nloglogn)$

埃式筛优化时间复杂度的原理：

考虑这样一件事情：对于任意一个大于 1 的正整数 n，那么它的 x 倍就是合数（x > 1）。利用这个结论，我们可以避免很多次不必要的检测。
如果我们从小到大考虑每个数，然后同时把当前这个数的所有（比自己大的）倍数记为合数，那么运行结束的时候没有被标记的数就是素数了。

 //埃式筛 
func InitPrime(maxNum int) map[int]struct{} {mp := make(map[int]struct{},maxNum)mp[1]  = struct{}{} //注意特判for i := 2; i <= maxNum; i ++ {if _,ok := mp[i]; ok { continue}for j := 2*i; j <= maxNum; j += i {mp[j] = struct{}{} //非素数}}return mp
}
func maximumPrimeDifference(nums []int) int {maxNum := 0for _,elem := range nums {if maxNum < elem {maxNum = elem}}primeMap := InitPrime(maxNum)minPos,maxPos := -1,-1for idx,elem := range nums {if _,ok := primeMap[elem];!ok {if minPos == -1 {minPos = idx}maxPos = idx}}return maxPos - minPos
}

思路5：欧拉筛

欧拉筛是在埃氏筛的基础上优化的，时间复杂度为$O(n)$

埃氏筛法仍有优化空间，它会将一个合数重复多次标记。有没有什么办法省掉无意义的步骤呢？答案是肯定的。
如果能让每个合数都只被标记一次，那么时间复杂度就可以降到 O(n) 了。

func InitPrime(maxNum int) map[int]struct{} {mp := make(map[int]struct{},maxNum)mp[1]  = struct{}{} //注意特判primes := make([]int,0,1000)for i := 2; i <= maxNum; i ++ {if _,ok := mp[i]; !ok { primes = append(primes,i)}for j := 0; primes[j] <= maxNum/i; j++ {mp[primes[j]*i] = struct{}{} //非素数if i % primes[j] == 0 {break}}}return mp
}
func maximumPrimeDifference(nums []int) int {maxNum := 0for _,elem := range nums {if maxNum < elem {maxNum = elem}}primeMap := InitPrime(maxNum)minPos,maxPos := -1,-1for idx,elem := range nums {if _,ok := primeMap[elem];!ok {if minPos == -1 {minPos = idx}maxPos = idx}}return maxPos - minPos
}

思路6： 打表

考虑到$1<=nums[i]<=100$，100以内的素数个数是有限的，离线把这些数据处理出来

func checkIsPrime(num int) bool {if num <= 1 {return false}for i := 2; i*i <= num; i ++ {if num % i == 0 {return false}}return true
}
func maximumPrimeDifference(nums []int) int {minPos,maxPos := -1,-1primes := []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}mp := make(map[int]struct{},len(primes))for _,elem := range primes {mp[elem] = struct{}{}}numsLen := len(nums)for idx := 0; idx < numsLen; idx ++ {if _,ok := mp[nums[idx]];ok {minPos = idxbreak}}for idx := numsLen - 1; idx >= 0; idx -- {if _,ok := mp[nums[idx]];ok {maxPos = idxbreak}}return maxPos - minPos
}