做网站运营工作流程,专业建站公司联系方式,番禺网站建设多少钱,搭建一个网站教程原题链接
题目描述
给你一个整数数组 nums。 返回两个#xff08;不一定不同的#xff09;质数在 nums 中 下标 的 最大距离。
示例 1#xff1a;
输入#xff1a; nums [4,2,9,5,3] 输出#xff1a; 3 解释#xff1a; nums[1]、nums[3] 和 nums[4] 是质数。因此答…原题链接
题目描述
给你一个整数数组 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 n u m s . l e n g t h 3 ∗ 1 0 5 1 nums.length 3 * 10^5 1nums.length3∗105 1 n u m s [ i ] 100 1 nums[i] 100 1nums[i]100 输入保证 nums 中至少有一个质数。
思路1一次遍历
函数checkIsPrime用于判断num是否为质数时间复杂度为 O ( s q r t ( n ) ) O(sqrt(n)) O(sqrt(n)) 一次遍历维护minPos表示最小的质数位置maxPos表示最大的质数位置最后maxPos-minPos就是答案 维护的时候如果该数是质数更新maxPos如果minPos未被更新过即minPos为初始值-1更新minPos
整体时间复杂度 O ( N ∗ s q r t ( M ) ) O(N*sqrt(M)) O(N∗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 ( n l o g l o g n ) O(nloglogn) 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) 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 n u m s [ i ] 100 1 nums[i] 100 1nums[i]100100以内的素数个数是有限的离线把这些数据处理出来
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
}
