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

标签: 贪心 数组 哈希表 二分查找 排序

难度: Medium

给你一个整数数组 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 <= 104
  • 1 <= banned[i], n <= 104
  • 1 <= maxSum <= 109

Submission

运行时间: 90 ms

内存: 17.7 MB

class Solution:
    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:
        ans, s = 0, set(banned)
        for i in range(1, n + 1):
            if i > maxSum: break
            if i not in s:
                maxSum -= i
                ans += 1
        return ans

Explain

这道题的思路是贪心算法。首先，将banned数组转换为集合s，便于快速查询某个整数是否被禁止。然后，从1开始遍历到n，对于每一个整数i，如果i不在s中且i小于等于maxSum，那么就将i加入到选择中，并且从maxSum中减去i，同时增加选择的整数数量ans。遍历结束后，ans即为最多可以选择的整数数目。

时间复杂度: O(n)

空间复杂度: O(banned.length)

class Solution:
    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:
        ans, s = 0, set(banned)  # 将banned数组转换为集合s
        for i in range(1, n + 1):  # 从1遍历到n
            if i > maxSum: break  # 如果当前整数大于maxSum，停止遍历
            if i not in s:  # 如果当前整数不在s中，即没有被禁止
                maxSum -= i  # 从maxSum中减去当前整数
                ans += 1  # 增加选择的整数数量
        return ans  # 返回最多可以选择的整数数目

Explore

将banned数组转换为集合的主要原因是集合（set）在Python中基于哈希表实现，因此查找操作的平均时间复杂度是O(1)。这使得在遍历整数时，检查一个数字是否被禁止变得非常高效。如果使用列表，查找操作的时间复杂度将是O(n)，这会导致总体算法效率降低。尽管字典也提供O(1)的查找效率，但它主要用于存储键值对，而在这种情况下，我们只需要一组唯一的值，因此集合是更合适的选择。

在这个算法中，由于我们从1开始递增地遍历到n，并且在每一步中尝试添加尽可能小的整数到选择中，一旦当前整数i大于剩余的maxSum，即使后续有更小的、未被禁止的整数也不可能被选中，因为所有后续整数都至少等于当前的i。因此，当i大于maxSum时停止遍历不会错过任何有效的选择。

这个贪心算法的基本思路是尽可能选择最小的、未被禁止的整数，以便使总和不超过maxSum。选择最小的数可以确保选择的整数数量最大化，因为用较小的数替代较大的数可以留出更多的空间来添加更多的数。这种策略的正确性基于这样一个事实：替换任何已选择的较大数（未超过maxSum且未被禁止）以获得更小的数总能增加可选择的数的数量，或至少保持不变。因此，这种策略可以保证选择的整数数量是最大的。

算法中将banned数组转换为集合的步骤并没有限定元素必须在[1, n]的范围内，这意味着集合s可能包含一些超出这个范围的元素。然而，这并不影响算法的准确性，因为在遍历和选择整数时，只考虑那些在[1, n]范围内且未被禁止的数。集合中超出范围的元素在遍历过程中不会被访问，因此不会影响结果。从效率的角度看，这可能略微增加了转换banned数组到集合的时间和空间成本，但这通常是可以接受的，除非banned数组非常大且大部分元素都在范围外。