张家界建设局网站电话号码,六安城市网官网,ppt模板简约,北京网站建设的服务题目链接 Leetcode.2601 质数减法运算 Rating #xff1a; 1779 题目描述
给你一个下标从 0 开始的整数数组 nums#xff0c;数组长度为 n 。
你可以执行无限次下述运算#xff1a;
选择一个之前未选过的下标 i #xff0c;并选择一个 严格小于 nums[i]的质数 ppp …题目链接 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 。 提示
1nums.length10001 nums.length 10001nums.length10001nums[i]10001 nums[i] 10001nums[i]1000nums.lengthnnums.length nnums.lengthn
解法筛素数 贪心 二分
由于 nums[i]nums[i]nums[i] 最大都只有 10310^3103所以我们可以把 100010001000以内的素数预处理出来存入 primesprimesprimes 数组中。
从后往前开始贪心假设当前遍历到 nums[i]nums[i]nums[i] 了(i0i 0i0)
如果 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代码
vectorint primes;
const int N 1e310;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(vectorint 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;}
};
