6355. 质数减法运算-JZTXT

方法：质数打表 + 二分

解题思路

每次将当前\(nums[i]\)减去一个质数（或不减），使得其变为为大于上一个数的最小值，可以给后面的元素更多减小的空间。

质数打表；
遍历数组\(nums\)，每次要和前一个数做比较，因此初始化前一个数为\(last\)。对于当前的\(num\)，选取使得\(num - prime > last\)的\(prime\)最大值，prime的选取可以对质数表进行二分。

代码

const int MX = 1000;
vector<int> prime{0}; // 避免二分越界

int init = []() {
    bool np[MX]{};
    for (int i = 2; i < MX; ++i)
        if (!np[i]) { // np[i] == false，是质数
            prime.push_back(i); // 预处理质数列表
            for (int j = i; j < MX / i; ++j)
                np[i * j] = true; // 不是质数
        }
    return 0;
}();

/*
    lambda匿名函数定义：[外部变量访问方式说明符] (参数) -> 返回值类型 { 函数体 };，
                        其中返回值类型如果未添加，会自动根据函数的返回值进行添加。
    因此上方相当于定义了函数 int f(void) {}，并调用f()。
*/

class Solution {
public:
    bool primeSubOperation(vector<int>& nums) {
        int last = 0;
        for (auto &num : nums) { // 每次将当前nums[i]减小到大于上一个数的最小值
            if (num <= last) return false; // 不符合递增要求
            last = num -  *--lower_bound(prime.begin(), prime.end(), num - last);
        }
        return true;
    }
};

复杂度分析

时间复杂度：\(O(nlogU)，U为质数表的数量\)；
空间复杂度：\(O(1)\)。