质数减法运算

难度: Medium

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

你可以执行无限次下述运算：

选择一个之前未选过的下标 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
nums.length == n

Submission

运行时间: 33 ms

内存: 16.2 MB

mx=1000+1
prime = []
is_prime = [True]*mx
for i in range(2,mx):
    if is_prime[i]:
        prime.append(i)
    for j in range(i * i, mx, i):
        is_prime[j] = False
prime.extend([mx,mx])
class Solution:
    def primeSubOperation(self, nums: List[int]) -> bool:
        for i in range(len(nums)-2,-1,-1):
            if nums[i+1] <2:
                return False
            if nums[i] >= nums[i+1]:
                if nums[i]<=2:
                    return False
                d = nums[i] - nums[i+1]
                t = prime[bisect.bisect_right(prime,d)]
                if t >= nums[i]:
                    return False
                nums[i] -= prime[bisect.bisect_right(prime,d)]
        return True

Explain

此题解采用了逆序处理数组元素的策略，从后向前调整数组，确保每个元素都比前一个元素小。首先，通过筛法（埃拉托斯特尼筛法）预先计算出所有1000以内的质数，并存储在数组中。对于数组中的每个元素，如果当前元素比后一个元素大或相等，则计算两者之差，并在质数列表中找到恰好大于此差的最小质数，使用该质数来减少当前元素的值。如果在任何点上，找到的质数大于或等于当前元素，或者后一个元素小于2（因为没有小于2的质数可以使用），则返回false。如果整个数组处理完毕没有遇到问题，则返回true。

时间复杂度: O(n log p)

空间复杂度: O(p)

mx=1000+1
prime = []
is_prime = [True]*mx
for i in range(2,mx):
    if is_prime[i]:
        prime.append(i)
    for j in range(i * i, mx, i):
        is_prime[j] = False
prime.extend([mx,mx])
class Solution:
    def primeSubOperation(self, nums: List[int]) -> bool:
        # 从后向前遍历数组，确保每个元素都比前一个小
        for i in range(len(nums)-2,-1,-1):
            if nums[i+1] <2:
                return False  # 后面的元素小于2，无法操作
            if nums[i] >= nums[i+1]:
                if nums[i]<=2:
                    return False  # 当前元素小于等于2，无法操作
                d = nums[i] - nums[i+1]  # 计算当前元素和后一个元素的差
                t = prime[bisect.bisect_right(prime,d)]  # 查找恰好大于差的质数
                if t >= nums[i]:
                    return False  # 如果质数大于等于当前元素，无法操作
                nums[i] -= prime[bisect.bisect_right(prime,d)]  # 更新当前元素的值
        return True

Explore

在逆序处理数组的时候，我们需要比较当前元素与其后一个元素的大小，并可能需要对当前元素进行调整。从倒数第二个元素开始是因为数组的最后一个元素没有后一个元素可以比较，所以从倒数第二个元素开始能确保每个参与比较的元素都有一个后续的元素。

在题解中，算法已经通过条件检查确保在减去质数之前，质数必须小于当前元素。这是通过检查质数是否大于等于当前元素来实现的。如果没有这个检查，当前元素减去一个大于自身的质数确实可能导致结果为负数，这会违背题目的逻辑要求。因此，这种情况在逻辑上被规避了。

检查质数是否大于等于当前元素是为了确保当前元素减去这个质数后不会变为负数或零。因为如果质数大于或等于当前元素，那么减去这个质数后的结果将不符合题目要求，即每个元素都应该是正整数。这样的检查是为了防止程序在运行过程中产生逻辑错误或不合理的结果。

基于质数的定义，质数是大于1的自然数且仅能被1和它本身整除的数。如果数组中的任何元素小于2，那么在减去任何质数后都不可能得到一个有效的正整数结果。因此，如果后一个元素小于2，就无法找到一个合适的质数来进行减法操作，从而无法继续执行题解中的逻辑。是的，所有元素必须大于1才能保证程序正常运行。