Medium

题目描述

给你一个长度为 n 的下标从 0 开始的整数数组 nums 。

你可以执行以下操作任意次：

  • 选择一个之前未选择过的下标 i ，并选择一个 严格小于 nums[i] 的质数 p ，然后从 nums[i] 中减去 p 。

如果你能通过上述操作使 nums 成为 严格递增 数组，则返回 true ；否则返回 false 。

严格递增数组 中每个元素都严格大于其前面的元素。

示例 1：

输入：nums = [4,9,6,10]
输出：true
解释：第一次操作中，选择 i = 0 和 p = 3，然后从 nums[0] 减去 3，nums 变为 [1,9,6,10]。
第二次操作中，i = 1，p = 7，从 nums[1] 减去 7，nums 变为 [1,2,6,10]。
第二次操作后，nums 按严格递增顺序排序，所以答案是 true。

示例 2：

输入：nums = [6,8,11,12]
输出：true
解释：nums 初始时已经是严格递增顺序，所以不需要进行任何操作。

示例 3：

输入：nums = [5,8,3]
输出：false
解释：可以证明无法通过操作使 nums 按严格递增顺序排序，所以答案是 false。

提示：

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 1000

解题思路

这道题的核心思路是贪心算法：对于每个位置，我们要找到最大的质数来减去，使得当前元素尽可能小但仍大于前一个元素。

算法步骤：

  1. 预处理质数：由于数值范围是1-1000，我们可以预先生成所有小于1000的质数，使用埃拉托斯特尼筛法。

  2. 贪心策略：从左到右遍历数组，对于每个位置i：

    • 如果nums[i] > nums[i-1]，可以选择不操作
    • 但为了让后续操作有更多空间，我们贪心地选择最大的质数p，使得nums[i] - p > nums[i-1]
    • 这样可以让nums[i]尽可能小，为后面的元素留出更多操作空间

  3. 找最大质数：对于当前元素nums[i]，我们需要找到最大的质数p，满足：

    • p < nums[i]（题目要求）
    • nums[i] - p > prev（保证严格递增，其中prev是前一个元素的值）

  4. 判断可行性：如果某个位置找不到合适的质数，说明无法构造严格递增序列。

时间复杂度主要在于预处理质数和对每个元素查找合适的质数。通过预处理，我们可以在O(1)时间内判断一个数是否为质数。

代码实现

class Solution {
public:
    bool primeSubOperation(vector<int>& nums) {
        // 预处理质数
        vector<bool> isPrime(1000, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i * i < 1000; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j < 1000; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        vector<int> primes;
        for (int i = 2; i < 1000; i++) {
            if (isPrime[i]) {
                primes.push_back(i);
            }
        }
        
        int prev = 0; // 前一个元素的值
        
        for (int i = 0; i < nums.size(); i++) {
            // 找到最大的质数p，使得nums[i] - p > prev
            int maxPrime = -1;
            for (int j = primes.size() - 1; j >= 0; j--) {
                if (primes[j] < nums[i] && nums[i] - primes[j] > prev) {
                    maxPrime = primes[j];
                    break;
                }
            }
            
            if (maxPrime != -1) {
                nums[i] -= maxPrime;
            }
            
            // 检查是否满足严格递增
            if (nums[i] <= prev) {
                return false;
            }
            
            prev = nums[i];
        }
        
        return true;
    }
};

class Solution:
    def primeSubOperation(self, nums: List[int]) -> bool:
        # 预处理质数
        def sieve(n):
            is_prime = [True] * n
            is_prime[0] = is_prime[1] = False
            for i in range(2, int(n**0.5) + 1):
                if is_prime[i]:
                    for j in range(i*i, n, i):
                        is_prime[j] = False
            return [i for i in range(2, n) if is_prime[i]]
        
        primes = sieve(1000)
        
        prev = 0  # 前一个元素的值
        
        for num in nums:
            # 找到最大的质数p，使得num - p > prev
            max_prime = -1
            for p in reversed(primes):
                if p < num and num - p > prev:
                    max_prime = p
                    break
            
            if max_prime != -1:
                num -= max_prime
            
            # 检查是否满足严格递增
            if num <= prev:
                return False
            
            prev = num
        
        return True

public class Solution {
    public bool PrimeSubOperation(int[] nums) {
        // 预处理质数
        bool[] isPrime = new bool[1000];
        Array.Fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        
        for (int i = 2; i * i < 1000; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j < 1000; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        List<int> primes = new List<int>();
        for (int i = 2; i < 1000; i++) {
            if (isPrime[i]) {
                primes.Add(i);
            }
        }
        
        int prev = 0; // 前一个元素的值
        
        for (int i = 0; i < nums.Length; i++) {
            // 找到最大的质数p，使得nums[i] - p > prev
            int maxPrime = -1;
            for (int j = primes.Count - 1; j >= 0; j--) {
                if (primes[j] < nums[i] && nums[i] - primes[j] > prev) {
                    maxPrime = primes[j];
                    break;
                }
            }
            
            if (maxPrime != -1) {
                nums[i] -= maxPrime;
            }
            
            // 检查是否满足严格递增
            if (nums[i] <= prev) {
                return false;
            }
            
            prev = nums[i];
        }
        
        return true;
    }
}

var primeSubOperation = function(nums) {
    // 预处理质数
    const sieve = (n) => {
        const isPrime = new Array(n).fill(true);
        isPrime[0] = isPrime[1] = false;
        
        for (let i = 2; i * i < n; i++) {
            if (isPrime[i]) {
                for (let j = i * i; j < n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        const primes = [];
        for (let i = 2; i < n; i++) {
            if (isPrime[i]) {
                primes.push(i);
            }
        }
        return primes;
    };
    
    const primes = sieve(1000);
    let prev = 0; // 前一个元素的值
    
    for (let i = 0; i < nums.length; i++) {
        // 找到最大的质数p，使得nums[i] - p > prev
        let maxPrime = -1;
        for (let j = primes.length - 1; j >= 0; j--) {
            if (primes[j] < nums[i] && nums[i] - primes[j] > prev) {
                maxPrime = primes[j];
                break;
            }
        }
        
        if (maxPrime !== -1) {
            nums[i] -= maxPrime;
        }
        
        // 检查是否满足严格递增
        if (nums[i] <= prev) {
            return false;
        }
        
        prev = nums[i];
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n × p)，其中n是数组长度，p是质数个数（约168个小于1000的质数）
空间复杂度O(p)，用于存储质数列表