2601-质数减法运算

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:24 2023-09-13 16:06:24 Updated    

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

本题视频讲解

见【周赛 338】 ，从 3:00 开始。

前置知识：二分查找

见【基础算法精讲 04】 。

前置知识：筛质数

见【周赛 326】 ，从 9:58 开始。

思路

设 pre 是上一个减完后的数字，x=\textit{nums}[i] 为当前数字。

设 p 是满足 x-p>\textit{pre 的最大质数，换言之，p 是小于 x-\textit{pre 的最大质数，这可以预处理质数列表后，用二分查找得到。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
MX = 1000
P = [0]  # 哨兵，避免二分越界
is_prime = [True] * MX
for i in range(2, MX):
    if is_prime[i]:
        P.append(i)  # 预处理质数列表
        for j in range(i * i, MX, i):
            is_prime[j] = False

class Solution:
    def primeSubOperation(self, nums: List[int]) -> bool:
        pre = 0
        for x in nums:
            if x <= pre: return False
            pre = x - P[bisect_left(P, x - pre) - 1]  # 减去 < x-pre 的最大质数
        return True
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    private final static int MX = 1000;
    private final static int[] primes = new int[169];

    static {
        var np = new boolean[MX + 1];
        int pi = 1; // primes[0] = 0 避免二分越界
        for (int i = 2; i <= MX; ++i)
            if (!np[i]) {
                primes[pi++] = i; // 预处理质数列表
                for (int j = i; j <= MX / i; ++j)
                    np[i * j] = true;
            }
    }

    public boolean primeSubOperation(int[] nums) {
        int pre = 0;
        for (int x : nums) {
            if (x <= pre) return false;
            int j = lowerBound(primes, x - pre);
            pre = x - primes[j - 1];
        }
        return true;
    }

    // 见 https://www.bilibili.com/video/BV1AP41137w7/
    private int lowerBound(int[] nums, int target) {
        int left = -1, right = nums.length; // 开区间 (left, right)
        while (left + 1 < right) { // 区间不为空
            // 循环不变量：
            // nums[left] < target
            // nums[right] >= target
            int mid = left + (right - left) / 2;
            if (nums[mid] < target)
                left = mid; // 范围缩小到 (mid, right)
            else
                right = mid; // 范围缩小到 (left, mid)
        }
        return right;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
const int MX = 1000;
vector<int> primes{0}; // 哨兵，避免二分越界

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

class Solution {
public:
    bool primeSubOperation(vector<int> &nums) {
        int pre = 0;
        for (int x: nums) {
            if (x <= pre) return false;
            pre = x - *--lower_bound(primes.begin(), primes.end(), x - pre);
        }
        return true;
    }
};
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
var p = []int{0} // 哨兵，避免二分越界

func init() {
	const mx = 1000
	np := [mx]bool{}
	for i := 2; i < mx; i++ {
		if !np[i] {
			p = append(p, i) // 预处理质数列表
			for j := i * i; j < mx; j += i {
				np[j] = true
			}
		}
	}
}

func primeSubOperation(nums []int) bool {
	pre := 0
	for _, x := range nums {
		if x <= pre {
			return false
		}
		pre = x - p[sort.SearchInts(p, x-pre)-1] // 减去 < x-pre 的最大质数
	}
	return true
}

复杂度分析

  • 时间复杂度：O(n\log U)，其中 n 为 nums 的长度，U 为 1000 以内的质数个数。
  • 空间复杂度：O(1)。忽略预处理的空间，仅用到若干额外变量。

相似题目

 Comments
On this page
2601-质数减法运算
  1. 本题视频讲解
  2. 前置知识：二分查找
  3. 前置知识：筛质数
  4. 思路
  5. 复杂度分析
  6. 相似题目