2601. 质数减法运算

🟠   🔖  贪心 数组 数学 二分查找 数论  🔗 力扣 LeetCode

题目

You are given a 0-indexed integer array nums of length n.

You can perform the following operation as many times as you want:

• Pick an index i that you haven't picked before, and pick a prime p strictly less than nums[i], then subtract p from nums[i].

Return true if you can makenums a strictly increasing array using the above operation and false otherwise.

A strictly increasing array is an array whose each element is strictly greater than its preceding element.

Example 1:

Input: nums = [4,9,6,10]

Output: true

Explanation: In the first operation: Pick i = 0 and p = 3, and then subtract 3 from nums[0], so that nums becomes [1,9,6,10].

In the second operation: i = 1, p = 7, subtract 7 from nums[1], so nums becomes equal to [1,2,6,10].

After the second operation, nums is sorted in strictly increasing order, so the answer is true.

Example 2:

Input: nums = [6,8,11,12]

Output: true

Explanation: Initially nums is sorted in strictly increasing order, so we don't need to make any operations.

Example 3:

Input: nums = [5,8,3]

Output: false

Explanation: It can be proven that there is no way to perform operations to make nums sorted in strictly increasing order, so the answer is false.

Constraints:

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 1000
• nums.length == n

题目大意

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

解题思路

1. 题目中的 nums[i] 范围在 1 <= nums[i] <= 1000，所以预生成小于等于 1000 的质数列表 primes，方便在每次操作中快速查找符合条件的质数。
2. 从 nums 的第一个元素开始，从质数列表中选择一个尽量大的质数 diff 进行减法操作，并使得 curVal 递增，以保证nums[i] 的值大于 nums[i-1]。
3. 若 diff 小于 0，也即 nums[i] 小于前一个元素 nums[i-1]，直接返回 false。
4. 如果在遍历整个 nums 的过程中，可以使每一个元素严格大于前一个元素，则返回 true。

复杂度分析

• 时间复杂度：O(n)，其中 n 是 nums 的长度。
• 空间复杂度：O(m)，用于存储所有小于等于 1000 的质数，最多需要 O(168)，即为常数时间复杂度。

代码

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var primeSubOperation = function (nums) {
	const primes = sieve(1000);
	let curVal = 1,
		i = 0;
	while (i < nums.length) {
		const diff = nums[i] - curVal;
		if (diff < 0) {
			return false;
		}
		if (diff == 0 || primes.includes(diff)) {
			i++;
			curVal++;
		} else {
			curVal++;
		}
	}
	return true;
};

/**
 * @param {number[]} nums
 * @return {boolean}
 */
function sieve(limit) {
	const isPrime = Array(limit + 1).fill(true);
	const primes = [];
	for (let i = 2; i <= limit; i++) {
		if (isPrime[i]) {
			primes.push(i);
			for (let j = i * i; j <= limit; j += i) {
				isPrime[j] = false;
			}
		}
	}
	return primes;
}