Leetcode.2601 质数减法运算

题目链接

Leetcode.2601 质数减法运算 rating : 1779

题目描述

给你一个下标从 $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\le nums.length\le 1000$
• $1\le nums[i]\le 1000$
• $nums.length=n$

解法：筛质数 + 贪心 + 二分

我们先使用 欧拉筛，筛出 $[1,n]$区间内所有的质数，存到 $primes$ 中。

筛质数

设 $pre$ 为前一个数，当前数为 $x$。设 $p$ 为小于 $x$ 的质数，我们要让 $pre<x-p$，并且$p$ 还必须是满足条件的最大质数。转换一下得到：

$$p<x-pre$$

等价于需要找到最后一个 小于 $x-pre$ 的质数 $p$，也就是满足该条件的最大质数。

• 如果 $pre\ge x$，说明不能使得当前 $nums$ 变成一个严格递增的数组，直接返回 false即可。
• 否则更新 $pre=x-p$，可以使用二分来快速的找到最大的质数 $p$。

时间复杂度：$O(n+n\times logn)$

C++代码：

const int N = 1010;
vector<bool> st(N, true);
vector<int> primes{0};

auto _ = []()
{
    for(int i = 2;i < N;i++)
    {
        if(st[i]) primes.push_back(i);
        for(int x: primes)
        {
            if(x == 0) continue;
            if(x * i >= N) break;
            st[i * x] = false;
            if(i % x == 0) break;
        }
    }

    return 0;
}();

class Solution {
public:
    bool primeSubOperation(vector<int>& nums) {
        int pre = 0;
        for(auto x:nums)
        {
            if(pre >= x) return false;
            auto it = lower_bound(primes.begin(), primes.end(), x - pre);
            --it;
            pre = x - *it;
        }

        return true;
    }
};

Python3代码：

primes = [0]
N = 1010
st = [True] * N

for i in range(2, N):
    if st[i]:
        primes.append(i)
    for x in primes:
        if x == 0:
            continue
        if x * i >= N:
            break
        st[x * i] = False
        if x % i == 0:
            break

class Solution:
    def primeSubOperation(self, nums: List[int]) -> bool:

        pre = 0
        for x in nums:
            if pre >= x:
                return False
            pre = x - primes[bisect_left(primes, x - pre) - 1]

        return True