题目描述
给你一个整数数组 banned
和两个整数 n
和 maxSum
。你需要按照以下规则选择一些整数:
- 被选择整数的范围是
[1, n]
。 - 每个整数 至多 选择 一次。
- 被选择整数不能在数组
banned
中。 - 被选择整数的和不超过
maxSum
。
请你返回按照上述规则 最多 可以选择的整数数目。
样例
输入:banned = [1,6,5], n = 5, maxSum = 6
输出:2
解释:你可以选择整数 2 和 4。
2 和 4 在范围 [1, 5] 内,且它们都不在 banned 中,它们的和是 6,没有超过 maxSum。
输入:banned = [1,2,3,4,5,6,7], n = 8, maxSum = 1
输出:0
解释:按照上述规则无法选择任何整数。
输入:banned = [11], n = 7, maxSum = 50
输出:7
解释:你可以选择整数 1, 2, 3, 4, 5, 6 和 7。
它们都在范围 [1, 7] 中,且都没出现在 banned 中,它们的和是 28,没有超过 maxSum。
限制
1 <= banned.length <= 10^4
1 <= banned[i], n <= 10^4
1 <= maxSum <= 10^9
算法
(贪心) $O(n + m)$
- 贪心的规则是尽可能选择小的数字。将
banned
存入哈希表。 - 从 $1$ 开始枚举,如果遇到
banned
中的数字,则跳过。否则,选择当前的数字。 - 直到达到 $maxSum$ 的限制。
时间复杂度
- 构造哈希表的时间复杂度为 $O(m)$。
- 最多枚举 $n$ 次,每次判定的时间为常数。
- 故总时间复杂度为 $O(n + m)$。
空间复杂度
- 需要 $O(m)$ 的额外空间存储哈希表。
C++ 代码
class Solution {
public:
int maxCount(vector<int>& banned, int n, int maxSum) {
unordered_set<int> b(banned.begin(), banned.end());
int ans = 0;
for (int i = 1; i <= n && maxSum >= i; i++) {
if (b.find(i) != b.end())
continue;
maxSum -= i;
ans++;
}
return ans;
}
};