Leetcode.2601 质数减法运算
题目链接
Leetcode.2601 质数减法运算 Rating : 1779
题目描述
给你一个下标从 0 开始的整数数组 nums
,数组长度为 n 。
你可以执行无限次下述运算:
- 选择一个之前未选过的下标 i ,并选择一个 严格小于
nums[i]
的质数 ppp ,从nums[i]
中减去 ppp 。
如果你能通过上述运算使得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<=10001 <= nums.length <= 10001<=nums.length<=1000
- 1<=nums[i]<=10001 <= nums[i] <= 10001<=nums[i]<=1000
- nums.length==nnums.length == nnums.length==n
解法:筛素数 + 贪心 + 二分
由于 nums[i]nums[i]nums[i] 最大都只有 10310^3103,所以我们可以把 100010001000以内的素数预处理出来,存入 primesprimesprimes 数组中。
从后往前开始贪心,假设当前遍历到 nums[i]nums[i]nums[i] 了(i>0i > 0i>0):
- 如果 nums[i]>nums[i−1]nums[i] > nums[i-1]nums[i]>nums[i−1],符合递增的要求,之间跳过本次循环
- 否则 nums[i]≤nums[i−1]nums[i] \\leq nums[i-1]nums[i]≤nums[i−1],我们将 nums[i−1]−nums[i]nums[i-1] - nums[i]nums[i−1]−nums[i] 的差值,记作 ddd:
-
- 我们通过 二分 的方式,从 primesprimesprimes 中找到第一个大于 ddd 的质数 ppp。
-
- 当 nums[i−1]>pnums[i-1] > pnums[i−1]>p 的情况下,nums[i−1]nums[i-1]nums[i−1] 才能减去 ppp ,否则返回 falsefalsefalse
- 循环结束返回 truetruetrue
时间复杂度: O(nlogn)O(nlogn)O(nlogn)
C++代码:
vector<int> primes;
const int N = 1e3+10;auto get_prime = [](){bool st[N + 1] = {};for(int i = 2;i <= N;i++){if(!st[i]) primes.push_back(i);for(auto p:primes){if(i * p > N) break;st[i * p] = true;if(i % p == 0) break;}}return 0;
}();class Solution {
public:bool primeSubOperation(vector<int>& nums) {int n = nums.size();for(int i = n - 1;i > 0;i--){if(nums[i] > nums[i-1]) continue;int d = nums[i-1] - nums[i];int idx = upper_bound(primes.begin(),primes.end(),d) - primes.begin();if(nums[i-1] > primes[idx]) nums[i - 1] -= primes[idx];else return false;}return true;}
};