当前位置: 首页 > news >正文

给一个网站做需求分析市场营销专业

给一个网站做需求分析,市场营销专业,wordpress变装网,进销存十大软件原题链接 题目描述 给你一个整数数组 nums。 返回两个(不一定不同的)质数在 nums 中 下标 的 最大距离。 示例 1: 输入: nums [4,2,9,5,3] 输出: 3 解释: 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 1<=nums.length<=3105
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(Nsqrt(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 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
}

在这里插入图片描述

http://www.fp688.cn/news/157676.html

相关文章:

  • 外贸网站如何做seoseo行业网
  • 长春网站建设电话营销培训课程
  • 常州男科医院哪一个好河源网站seo
  • 凡科轻站小程序收费吗苹果cms永久免费全能建站程序
  • 一家只做正品的网站新东方雅思培训机构官网
  • 有哪些做外贸免费的网站如何让百度收录自己信息
  • 网站 备案 公安网络搜索引擎优化
  • 软件开发合同模板范本电子商务seo是什么意思
  • 郑州做网站公司排名seo搜狗排名点击
  • 5118网站是免费的吗百度信息流优化
  • 店招搜索栏在那个网站上可以做软文撰写公司
  • 98建筑人才网佛山优化网站关键词
  • 外贸网站设计师怎么给公司做网站推广
  • 制作个人网站教程全国十大跨境电商排名
  • 外贸电商网站制作建立网站的详细步骤
  • 传媒公司 网站开发公关公司提供的服务有哪些
  • 如何判断网站数据库类型外链生成网站
  • 人工智能自动做网站百度竞价课程
  • 做受视频播放网站seo平台
  • 微信分销算b2c网站吗营销推广网
  • 企业网站怎么做优化可以进入任何网站的浏览器
  • 大数据培训班需要多少钱成都seo优化公司排名
  • 网站制作需要哪些上海最大的seo公司
  • 微站是什么东西站长之家ip查询
  • 视频网站VIP卡怎么做赠品成都seo培
  • 个人网站怎么做银行卡支付宝网页设计主题参考
  • 微网站设计方案营销战略包括哪些方面
  • 做网站开专票税钱是多少个点9个成功的市场营销案例
  • 做公司的网站有哪些东西免费注册网址
  • 保定网站制作公司代写平台