题目描述
给你一个整数数组 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
1<=nums.length<=3∗105
1
<
=
n
u
m
s
[
i
]
<
=
100
1 <= nums[i] <= 100
1<=nums[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,-1
for 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,-1
for idx,elem := range nums {
if checkIsPrime(elem) {
minPos = idx
break
}
}
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,-1
mp := 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 = idx
mp[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 := 0
for _,elem := range nums {
if maxNum < elem {
maxNum = elem
}
}
primeMap := InitPrime(maxNum)
minPos,maxPos := -1,-1
for 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 := 0
for _,elem := range nums {
if maxNum < elem {
maxNum = elem
}
}
primeMap := InitPrime(maxNum)
minPos,maxPos := -1,-1
for 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 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,-1
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}
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 = idx
break
}
}
for idx := numsLen - 1; idx >= 0; idx -- {
if _,ok := mp[nums[idx]];ok {
maxPos = idx
break
}
}
return maxPos - minPos
}
