原題鏈接

題目描述

給你一個整數數組 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?10^5$
$1<=nums[i]<=100$
輸入保證 nums 中至少有一個質數。

思路1：一次遍歷

函數checkIsPrime用于判斷num是否為質數，時間復雜度為$O(sqrt(n))$
一次遍歷，維護minPos表示最小的質數位置，maxPos表示最大的質數位置，最后maxPos-minPos就是答案
維護的時候，如果該數是質數，更新maxPos；如果minPos未被更新過，即minPos為初始值-1，更新minPos

整體時間復雜度$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(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
}