2554. 从一个范围内选择最多整数 I

🟠   🔖  贪心 数组 哈希表 二分查找 排序  🔗 力扣 LeetCode

题目

You are given an integer array banned and two integers n and maxSum. You are choosing some number of integers following the below rules:

• The chosen integers have to be in the range [1, n].
• Each integer can be chosen at most once.
• The chosen integers should not be in the array banned.
• The sum of the chosen integers should not exceed maxSum.

Return themaximum number of integers you can choose following the mentioned rules.

Example 1:

Input: banned = [1,6,5], n = 5, maxSum = 6

Output: 2

Explanation: You can choose the integers 2 and 4.

2 and 4 are from the range [1, 5], both did not appear in banned, and their sum is 6, which did not exceed maxSum.

Example 2:

Input: banned = [1,2,3,4,5,6,7], n = 8, maxSum = 1

Output: 0

Explanation: You cannot choose any integer while following the mentioned conditions.

Example 3:

Input: banned = [11], n = 7, maxSum = 50

Output: 7

Explanation: You can choose the integers 1, 2, 3, 4, 5, 6, and 7.

They are from the range [1, 7], all did not appear in banned, and their sum is 28, which did not exceed maxSum.

Constraints:

• 1 <= banned.length <= 10^4
• 1 <= banned[i], n <= 10^4
• 1 <= maxSum <= 10^9

题目大意

给你一个整数数组 banned 和两个整数 n 和 maxSum 。你需要按照以下规则选择一些整数：

• 被选择整数的范围是 [1, n] 。
• 每个整数 至多 选择 一次 。
• 被选择整数不能在数组 banned 中。
• 被选择整数的和不超过 maxSum 。

请你返回按照上述规则 最多 可以选择的整数数目。

示例 1：

输入： banned = [1,6,5], n = 5, maxSum = 6

输出： 2

解释： 你可以选择整数 2 和 4 。

2 和 4 在范围 [1, 5] 内，且它们都不在 banned 中，它们的和是 6 ，没有超过 maxSum 。

示例 2：

输入： banned = [1,2,3,4,5,6,7], n = 8, maxSum = 1

输出： 0

解释： 按照上述规则无法选择任何整数。

示例 3：

输入： 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

解题思路

1. 利用一个 Set 存储禁止的数字 banned，以便快速查询某个数字是否被禁止。
2. 定义两个变量：count 表示已选择的数字个数，sum 表示当前已选择数字的总和。
3. 贪心选择数字：从 1 到 n 依次遍历每个数字，按照从小到大的顺序尝试将其加入总和 sum 中。
   • 如果当前数字不在 Set 中，并且加入后 sum 不超过 maxSum，则将其计入结果，并更新总和 sum 和计数 count。
   • 如果当前数字加入后总和超过 maxSum，则可以直接终止循环（后续的数字只会更大，无法满足条件）。
4. 返回最终的 count。

复杂度分析

• 时间复杂度：O(n + b)，其中 b 是 banned 的长度。
  • 创建 Set 的复杂度为 O(b)；
  • 遍历范围 1 到 n，每次检查数字是否在 banned 集合中，时间复杂度为 O(n)；
  • 总时间复杂度为 O(n + b)。
• 空间复杂度：O(b)，Set 用于存储 banned 列表。

代码

/**
 * @param {number[]} banned
 * @param {number} n
 * @param {number} maxSum
 * @return {number}
 */
var maxCount = function (banned, n, maxSum) {
	// 用 Set 存储 banned 列表
	let set = new Set(banned);
	let count = 0,
		sum = 0;

	// 从 1 遍历到 n
	for (let i = 1; i <= n; i++) {
		let curSum = sum + i;
		// 如果数字未被禁止且总和不超过 maxSum
		if (!set.has(i) && curSum <= maxSum) {
			count++;
			sum = curSum;
		} else if (curSum > maxSum) {
			// 当前数字超过 maxSum，直接退出循环
			break;
		}
	}
	return count;
};

相关题目

题号	标题	题解	标签	难度	力扣
41	缺失的第一个正数	[✓]	数组 哈希表	🔴	🀄️ 🔗
448	找到所有数组中消失的数字	[✓]	数组 哈希表	🟢	🀄️ 🔗
2195	向数组中追加 K 个整数		贪心 数组 数学 1+	🟠	🀄️ 🔗
2295	替换数组中的元素		数组 哈希表 模拟	🟠	🀄️ 🔗
2557	从一个范围内选择最多整数 II 🔒		贪心 数组 二分查找 1+	🟠	🀄️ 🔗