时间轴

2025-10-16

init

题目：

P2598 执行操作后的最大 MEX

https://leetcode.cn/problems/smallest-missing-non-negative-integer-after-operations/description/?envType=daily-question&envId=2025-10-16

TLE

用最小堆存储nums中各个数取绝对值并取value余数的值，然后从最小值开始数，如果最小堆弹出的值和当前数的值相同，那么把它+value后压回栈。重复此过程，直到栈空或者出现不连续的值。但这种方法O(nlogn)会超时

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <vector>
#include <algorithm>
#include <queue>

using std::priority_queue;
using std::vector;

class Solution {
    public:
	int cel_div(int a, int b)
	{
		return (a + b - 1) / b;
	}
	int findSmallestInteger(vector<int> &nums, int value)
	{
		// 先将所有负数变为正数
		// 再将所有数变为除以value的余数

		int i;
		int n = nums.size();
		int top_value;
		int last_value;
		int count = 0;
		priority_queue<int, vector<int>, std::greater<int> > min_heap;

		for (i = 0; i < n; i++) {
			if (nums[i] < 0) {
				nums[i] += cel_div(-nums[i], value) * value;
			}
			nums[i] = nums[i] % value;
			min_heap.push(nums[i]);
		}

		last_value = -1;

		while (!min_heap.empty()) {
			top_value = min_heap.top();
			if (top_value == last_value) {
				min_heap.pop();
				min_heap.push(top_value + value);
				continue;
			}
			if (top_value != last_value + 1) {
				break;
			} else {
				last_value = top_value;
				min_heap.pop();
			}
		}

		return last_value + 1;
	}
};

int main()
{
	vector<int> vec = { 3, 0, 3, 2, 4, 2, 1, 1, 0, 4 };
	int value = 5;
	Solution s;
	s.findSmallestInteger(vec, value);
}

数学上优化

value的余数的所有可能取值为一组，假设有group组value的余数的所有可能取值，那么最终数组最大至少取到$value \times group -1$，从nums中去掉这些组的值，剩下的里面，必定缺少value余数的所有可能取值中的一个，我们找缺少的最小值加上$value \times group -1$即可。编程来看就是统计各个余数的个数，找个数中最小的那个为group，最小的当然不能为0，

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <vector>
#include <algorithm>
#include <climits>
#include <unordered_map>

using std::vector;
using std::unordered_map;

class Solution {
    public:
	int cel_div(int a, int b)
	{
		return (a + b - 1) / b;
	}
	int findSmallestInteger(vector<int> &nums, int value)
	{
		// 先将所有负数变为正数
		// 再将所有数变为除以value的余数

		int i;
		int n = nums.size();
		int group = INT_MAX;

		int res;

		unordered_map<int, int> umap;

		if (value == 1) {
			return n - 1;
		}

		for (i = 0; i < n; i++) {
			if (nums[i] < 0) {
				nums[i] += cel_div(-nums[i], value) * value;
			}
			nums[i] = nums[i] % value;
			umap[nums[i]]++;
		}

		for (i = 0; i < value; i++) {
			if (umap.count(i) == 0) {
				return i;
			}
		}

		for (auto &[num, count] : umap) {
			if (count < group) {
				group = count;
				res = num;
			} else if (count == group) {
				res = std::min(res, num);
			}
		}

		res += group * value - 1;

		return res;
	}
};

int main()
{
	vector<int> vec = { 3, 2, 3, 1, 0, 1, 4, 2, 3, 1, 4, 1, 3 };
	int value = 5;
	Solution s;
	s.findSmallestInteger(vec, value);
}