【力扣 - 每日一题】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 * 10^5$
$1 <= n u m s [i] <= 100$
输入保证 nums 中至少有一个质数。

思路1：一次遍历

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

整体时间复杂度 $O (N * s q r t (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)$

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

考虑这样一件事情：对于任意一个大于 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) 了。

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$ ，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
}