2026-07-26将数组转换为交替质数数组的最少操作次数。用go语言给定一个整数数组nums你需要通过最少的操作次数把它变成满足特定规律的数组。规律是数组中所有索引为偶数的位置最终的值必须是质数。所有索引为奇数的位置最终的值必须是非质数。每次操作只能让任意位置的元素加 1。目标是求出让整个数组满足这个条件所需的最少操作次数。1 nums.length 100000。1 nums[i] 100000。输入 nums [1,2,3,4]。输出 3。解释下标 0 处的元素必须是质数。将 nums[0] 1 增加到 2使用 1 次操作。下标 1 处的元素必须是非质数。将 nums[1] 2 增加到 4使用 2 次操作。下标 2 处的元素已经是质数。下标 3 处的元素已经是非质数。总操作次数 1 2 3。题目来自力扣3896。大体步骤如下一、质数预计算阶段在init()函数中代码预先构建了一个质数标记数组notPrime长度为100_004。初始化标记数组notPrime[0]和notPrime[1]被标记为1因为 0 和 1 不是质数。其余位置初始为0表示暂时认为是质数。埃拉托色尼筛法从 2 开始遍历只要i * i mx即i 316左右检查notPrime[i]。如果notPrime[i] 0说明 i 是质数则将 i 的所有倍数从i * i开始标记为1非质数。筛选完成后notPrime[p] 0表示 p 是质数notPrime[p] 1表示 p 不是质数。这里的数组大小取100_004是因为题目中元素最大值是 100000而操作是不断增加数值可能超出原最大值。选用大于 1e5 的下一个质数 100003 再加 1确保在增加过程中查询质数属性时不越界。二、主处理过程minOperations函数遍历输入数组nums对每个元素根据其索引的奇偶性进行不同处理并累加操作次数。遍历数组用for i, x : range nums同时获取索引i和对应的值x。确定目标条件如果i是偶数i % 2 0要求该位置的最终值必须是质数即notPrime[x]最终应该等于0。如果i是奇数i % 2 1要求该位置的最终值必须是非质数即notPrime[x]最终应该等于1。用i % 2正好可以表达这个期望值偶数索引期望notPrime[x] 0奇数索引期望notPrime[x] 1内层循环递增对于当前位置的数值x检查notPrime[x]是否等于i % 2如果不等说明当前值不满足条件。由于只能做“加 1”操作于是将x增加 1同时操作次数ans加 1然后再次判断新x是否满足条件。循环终止条件当notPrime[x] i % 2时停止此时x满足该索引位置的要求偶数索引时 x 是质数奇数索引时 x 是非质数。这个循环保证了每个元素通过最少次数的“加 1”操作达到离它最近的一个满足条件的值向上搜索第一个符合条件的数。累加结果每处理完一个元素其所需的操作次数已经累加到ans中。遍历结束后ans就是整个数组变为交替质数/非质数数组的最少总操作次数。三、示例执行过程以nums [1, 2, 3, 4]为例i0偶数期望质数x1notPrime[1] 1 ≠ 0递增到 2质数操作 1。i1奇数期望非质数x2notPrime[2] 0 ≠ 1递增到 3质数操作 1仍不满足递增到 4非质数操作 1共 2。i2偶数期望质数x3notPrime[3] 0 0已满足操作 0。i3奇数期望非质数x4notPrime[4] 1 1已满足操作 0。总操作次数 1 2 0 0 3。四、时间复杂度分析质数预计算埃氏筛的时间复杂度为 O(M log log M)其中 M 100004。这是一个常数上限所以是 O(1)。主循环对数组中每个元素内层的for循环会让x递增直到找到符合条件的值。在最坏情况下每次可能跨越多个数但每个数最多递增到下一个符合条件的值而质数和非质数的间隔是有限的。由于质数分布相对密集在 1e5 范围内最大间隔不超过几百实际上内层循环执行次数与数组长度 n 成线性关系总体可以认为是 O(n)。如果严格分析每个位置的操作次数等于“到达下一个符合条件的数的距离”所有距离之和不会超过某个常数乘以 n因为数值范围有限质数间隙有界因此仍是 O(n)。总时间复杂度O(n)其中 n 是数组长度。五、空间复杂度分析notPrime 数组大小为 100004 的整型数组占用常数级额外空间O(1)。其他变量只用了几个整型变量i, x, ans 等O(1)。总额外空间复杂度O(1)。Go完整代码如下packagemainimport(fmt)constmx100_004// 1e5 的下一个质数是 1e5 3varnotPrime[mx]int{1,1}funcinit(){fori:2;i*imx;i{ifnotPrime[i]0{forj:i*i;jmx;ji{notPrime[j]1}}}}funcminOperations(nums[]int)(ansint){fori,x:rangenums{// 如果 i 是偶数那么循环直到 notPrime[x] 0x 是质数// 如果 i 是奇数那么循环直到 notPrime[x] 1x 不是质数fornotPrime[x]!i%2{ansx}}return}funcmain(){nums:[]int{1,2,3,4}result:minOperations(nums)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-defmin_operations(nums):mx100004# 1e5 的下一个质数是 1e5 3not_prime[0]*mx not_prime[0]not_prime[1]1# 埃氏筛标记非质数foriinrange(2,int(mx**0.5)1):ifnot_prime[i]0:forjinrange(i*i,mx,i):not_prime[j]1ans0fori,xinenumerate(nums):# 如果 i 是偶数需要 not_prime[x] 0x 是质数# 如果 i 是奇数需要 not_prime[x] 1x 不是质数whilenot_prime[x]!i%2:ans1x1returnansif__name____main__:nums[1,2,3,4]resultmin_operations(nums)print(result)C完整代码如下#includeiostream#includevectorusingnamespacestd;constintmx100004;// 1e5 的下一个质数是 1e5 3intnotPrime[mx]{1,1};// 初始化埃氏筛voidinit(){for(inti2;i*imx;i){if(notPrime[i]0){for(intji*i;jmx;ji){notPrime[j]1;}}}}intminOperations(vectorintnums){intans0;for(inti0;inums.size();i){intxnums[i];// 如果 i 是偶数需要 notPrime[x] 0x 是质数// 如果 i 是奇数需要 notPrime[x] 1x 不是质数while(notPrime[x]!i%2){ans;x;}}returnans;}intmain(){init();// 初始化质数表vectorintnums{1,2,3,4};intresultminOperations(nums);coutresultendl;return0;}
