Medium
题目描述
给你一个整数数组 nums。
如果一个数组满足以下条件，则称为交替质数数组：
- 偶数索引（从0开始）的元素是质数
- 奇数索引的元素是非质数
在一次操作中，你可以将任意元素增加1。
返回将 nums 转换为交替质数数组所需的最少操作次数。
质数是大于1且只有两个因子（1和它本身）的自然数。
示例 1：
输入：nums = [1,2,3,4]
输出：3
解释：
- 索引0的元素必须是质数。将 nums[0] = 1 增加到 2，需要1次操作。
- 索引1的元素必须是非质数。将 nums[1] = 2 增加到 4，需要2次操作。
- 索引2已经是质数。
- 索引3已经是非质数。
总操作次数 = 1 + 2 = 3。
示例 2：
输入：nums = [5,6,7,8]
输出：0
解释：
- 索引0和2的元素已经是质数。
- 索引1和3的元素已经是非质数。
不需要操作。
示例 3：
输入：nums = [4,4]
输出：1
解释：
- 索引0的元素必须是质数。将 nums[0] = 4 增加到 5，需要1次操作。
- 索引1已经是非质数。
总操作次数 = 1。
约束条件：
1 <= nums.length <= 10^51 <= nums[i] <= 10^5
解题思路
解题思路：
这道题要求将数组转换为交替质数模式，即偶数位置必须是质数，奇数位置必须是非质数。我们可以独立处理每个位置，找到满足条件的最小值。
主要思路：
- 预计算质数表：使用埃拉托斯特尼筛法预计算所有小于等于最大可能值的质数，便于快速判断
- 分别处理偶数和奇数位置：
- 偶数位置：找到大于等于当前值的最小质数
- 奇数位置：找到大于等于当前值的最小非质数
- 优化非质数查找：对于奇数位置，如果当前数已经是非质数则不需要操作；否则，除了2和3这两个特殊情况，大部分数字最多增加1就能变成非质数
关键观察：
- 对于偶数位置，我们需要预先计算好所有质数，然后二分查找或直接遍历找到下一个质数
- 对于奇数位置，1和所有合数都是非质数，只有质数需要增加到下一个非质数
- 由于每个位置都可以独立处理，总的操作次数就是所有位置操作次数的和
代码实现
class Solution {
public:
int minOperations(vector<int>& nums) {
const int MAXN = 100001;
vector<bool> isPrime(MAXN, true);
isPrime[0] = isPrime[1] = false;
// 埃拉托斯特尼筛法
for (int i = 2; i * i < MAXN; i++) {
if (isPrime[i]) {
for (int j = i * i; j < MAXN; j += i) {
isPrime[j] = false;
}
}
}
int operations = 0;
for (int i = 0; i < nums.size(); i++) {
if (i % 2 == 0) { // 偶数位置需要质数
int val = nums[i];
while (val < MAXN && !isPrime[val]) {
val++;
}
operations += val - nums[i];
} else { // 奇数位置需要非质数
int val = nums[i];
if (val == 1 || !isPrime[val]) {
// 已经是非质数，不需要操作
continue;
}
// 找到下一个非质数
val++;
while (val < MAXN && isPrime[val]) {
val++;
}
operations += val - nums[i];
}
}
return operations;
}
};
class Solution:
def minOperations(self, nums: list[int]) -> int:
MAXN = 100001
is_prime = [True] * MAXN
is_prime[0] = is_prime[1] = False
# 埃拉托斯特尼筛法
for i in range(2, int(MAXN**0.5) + 1):
if is_prime[i]:
for j in range(i * i, MAXN, i):
is_prime[j] = False
operations = 0
for i, num in enumerate(nums):
if i % 2 == 0: # 偶数位置需要质数
val = num
while val < MAXN and not is_prime[val]:
val += 1
operations += val - num
else: # 奇数位置需要非质数
if num == 1 or not is_prime[num]:
# 已经是非质数，不需要操作
continue
# 找到下一个非质数
val = num + 1
while val < MAXN and is_prime[val]:
val += 1
operations += val - num
return operations
public class Solution {
public int MinOperations(int[] nums) {
const int MAXN = 100001;
bool[] isPrime = new bool[MAXN];
Array.Fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
// 埃拉托斯特尼筛法
for (int i = 2; i * i < MAXN; i++) {
if (isPrime[i]) {
for (int j = i * i; j < MAXN; j += i) {
isPrime[j] = false;
}
}
}
int operations = 0;
for (int i = 0; i < nums.Length; i++) {
if (i % 2 == 0) { // 偶数位置需要质数
int val = nums[i];
while (val < MAXN && !isPrime[val]) {
val++;
}
operations += val - nums[i];
} else { // 奇数位置需要非质数
int val = nums[i];
if (val == 1 || !isPrime[val]) {
// 已经是非质数，不需要操作
continue;
}
// 找到下一个非质数
val++;
while (val < MAXN && isPrime[val]) {
val++;
}
operations += val - nums[i];
}
}
return operations;
}
}
var minOperations = function(nums) {
function isPrime(n) {
if (n < 2) return false;
if (n === 2) return true;
if (n % 2 === 0) return false;
for (let i = 3; i * i <= n; i += 2) {
if (n % i === 0) return false;
}
return true;
}
function isNonPrime(n) {
return n > 1 && !isPrime(n);
}
let operations = 0;
for (let i = 0; i < nums.length; i++) {
if (i % 2 === 0) {
// Even index - need prime
let current = nums[i];
while (!isPrime(current)) {
current++;
operations++;
}
} else {
// Odd index - need non-prime
let current = nums[i];
while (!isNonPrime(current)) {
current++;
operations++;
}
}
}
return operations;
};
复杂度分析
| 项目 | 复杂度 |
|---|---|
| 时间复杂度 | O(n log log MAXN + n × k)，其中 n 是数组长度，MAXN = 100001，k 是找到下一个质数/非质数的平均步数 |
| 空间复杂度 | O(MAXN) |
说明：
- 时间复杂度中，O(n log log MAXN) 来自埃拉托斯特尼筛法预处理质数表
- O(n × k) 来自遍历数组并为每个位置找到合适的质数或非质数，k 通常很小
- 空间复杂度主要用于存储质数判断表