给你一个下标从 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

思路分析

逆向思考，从后往前找，记录last
如果当前x < last,则continue
如果当前x >= last,则x - p < last (x-p要足够的大，则p需要足够的小),等价于 p > x - last,p是比x-last大的最小质数
WA注意：需要额外增加一个质数，可以把N设置大一些。
如果 last <= 0,说明当前的p并没有严格小于x，返回False
例如[5,3,8]
last = inf,x = 3,3 < inf,last = 3
last = 3, x = 8,8 > 3, last = 8 - 7 = 1
last = 1, x = 5,5 > 1, last = 5 - 5 = 0(没有严格递增)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# 预处理
MX = 10 ** 4 + 1
primes = [0]
is_prime = [True] * MX
for i in range(2, MX):
    if is_prime[i]:
        primes.append(i)
        for j in range(i * i, MX, i):
            is_prime[j] = False
class Solution:
    # 正向思考
    def primeSubOperation_1(self, nums: List[int]) -> bool:
        pre = 0
        for i,x in enumerate(nums):
            if x <= pre:
                return False
            idx = bisect.bisect_left(primes,x - pre)-1
            pre = x - primes[idx]
        return True

    # 逆向思考
    def primeSubOperation(self, nums: List[int]) -> bool:
        last = inf
        n = len(nums)
        for i in range(n-1,-1,-1):
            x = nums[i]
            if x < last:
                last = x
                continue
            else:
                idx = bisect.bisect_left(primes,x - last + 10e-9)
                last = x - primes[idx]
            
            if last <= 0:
                return False
        return True

灵神代码

设pre是上一个减完后的数字，x=nums[i] 为当前数字。
设p是满足x−p>pre 的最大质数，换言之p 是小于x−pre 的最大质数，这可以预处理质数列表后，用二分查找得到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
MX = 1000
P = [0]  # 哨兵，避免二分越界
is_prime = [True] * MX
for i in range(2, MX):
    if is_prime[i]:
        P.append(i)  # 预处理质数列表
        for j in range(i * i, MX, i):
            is_prime[j] = False

class Solution:
    def primeSubOperation(self, nums: List[int]) -> bool:
        pre = 0
        for x in nums:
            if x <= pre: return False
            pre = x - P[bisect_left(P, x - pre) - 1]  # 减去 < x-pre 的最大质数
        return True

复杂度分析

时间复杂度：O()，其中 n 为 nums 的长度，U 为 1000 以内的质数个数。
空间复杂度：O(1)