从范围 I 中选择的最大整数数

2554。从范围 I

中选择的最大整数数

难度：中等

主题：数组、哈希表、二分查找、贪婪、排序

给你一个被禁止的整数数组和两个整数 n 和 maxSum。您将按照以下规则选择一些整数：

• 所选整数必须在 [1, n] 范围内。
• 每个整数可以选择最多一次。
• 所选整数不应出现在禁止的数组中。
• 所选整数的总和不应超过 maxSum。

返回您可以按照上述规则选择的最大个整数。

示例1：

• 输入： 禁止 = [1,6,5], n = 5, maxSum = 6
• 输出： 2
• 说明：您可以选择整数 2 和 4。
  • 2和4都来自[1, 5]范围，都没有出现在banned中，它们的和是6，没有超过maxSum。

示例2：

• 输入： 禁止 = [1,2,3,4,5,6,7], n = 8, maxSum = 1
• 输出： 0
• 说明：在满足上述条件的情况下不能选择任何整数。

示例 3：

• 输入： 禁止 = [11]，n = 7，maxSum = 50
• 输出： 7
• 说明：您可以选择整数 1、2、3、4、5、6 和 7。
  • 它们都来自[1, 7]范围，都没有出现在banned中，它们的总和是28，没有超过maxSum。

约束：

• 1 4
• 1 4
• 1 9

提示：

1. 将小于 n 的禁用号码保留在一组中。
2. 循环从1到n的数字，如果该数字没有被禁止，则使用它。
3. 在未被禁止的情况下不断相加，并且它们的总和小于k。

解决方案：

我们可以使用贪心方法，迭代从 1 到 n 的数字，跳过禁止的数字，并继续将有效数字（不在禁止数组中的数字）添加到运行总和中，直到达到 maxSum。

以下是分步解决方案：

步骤：

1. 将禁止数组转换为集合以进行快速查找：使用 array_flip() 可以将禁止数组转换为集合以进行 O(1) 平均时间复杂度查找。
2. 从 1 迭代到 n： 检查每个数字，如果它不在禁止的集合中，并且如果相加没有超过 maxSum，则将其添加到总和中并增加计数。
3. 一旦添加下一个数字超过 maxSum 就停止：由于目标是最大化所选整数的数量而不超过总和，因此这种贪心方法确保我们首先获取最小的可用数字。

方法：

1. 排除禁用号码：我们将跟踪集合（或关联数组）中的禁用号码，以便快速查找。
2. 贪婪选择： 开始按升序选择从 1 到 n 的数字，因为这将使我们能够最大化所选整数的数量。每次我们选择一个数字时，我们都会将其添加到总和中并检查它是否超过 maxSum。如果是这样，请停止。
3. 效率考虑因素：由于我们迭代从 1 到 n 的数字，并检查每个数字是否在禁止集中（这可以在恒定时间内完成），因此该方法以相对于 n 的线性时间运行，并且禁止列表的大小。

让我们用 PHP 实现这个解决方案：2554。从范围 I
中选择的最大整数数

<?php
/**
 * @param Integer[] $banned
 * @param Integer $n
 * @param Integer $maxSum
 * @return Integer
 */
function maxCount($banned, $n, $maxSum) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo maxCount([1, 6, 5], 5, 6);  // Output: 2
echo "\n";
echo maxCount([1, 2, 3, 4, 5, 6, 7], 8, 1);  // Output: 0
echo "\n";
echo maxCount([11], 7, 50);  // Output: 7
?>

解释：

1. 将禁用数组转换为设置：
   
   我们使用 array_flip($banned) 从被禁止的数组中创建一个集合，这允许 O(1) 查找来检查某个数字是否被禁止。

2. 从 1 迭代到 n：
   
   我们迭代从 1 到 n 的数字。对于每个数字：

   • 如果号码不在禁止集中（使用 isset($bannedSet[$i]) 检查），
   • 如果将数字添加到总和中不超过 maxSum，
   • 我们包含该数字并更新总和和计数。

3. 返回计数：
   
   循环结束后，我们返回所选整数的数量 ($count)。

4. $bannedSet = array_flip($banned);：这会将禁止列表转换为集合（关联数组）以进行快速查找。

5. for ($i = 1; $i ：我们迭代从 1 到 n 的所有整数。

6. if (isset($bannedSet[$i])) { 继续; }：检查当前号码是否在禁止集中。如果是，我们就跳过它。

7. if ($sum $i > $maxSum) {break; }：如果添加当前数字超过 maxSum，我们将停止该过程。

8. $sum = $i; $count ;：如果数字有效并且相加不超过 maxSum，我们将其包含在总和中并增加计数。

时间复杂度：

• 禁止集合（array_flip）的创建是 O(b)，其中 b 是禁止数组的长度。
• 循环迭代 n 次（对于从 1 到 n 的数字），每次查找禁止集合都需要 O(1) 时间。所以，循环的时间复杂度是O(n)。
• 因此，总体时间复杂度为 O(n b)，在给定问题约束的情况下，这是有效的。

演练示例：

输入：

• 输入 1: 禁止 = [1, 6, 5], n = 5, maxSum = 6

  • 我们创建禁止集：{1, 5, 6}。
  • 我们迭代数字 1 到 5：
    • 1 已禁止，请跳过。
    • 2不被禁止，将其添加到sum（sum = 2，count = 1）。
    • 3不被禁止，将其添加到sum（sum = 5，count = 2）。
    • 4 并不被禁止，但将其添加到总和中会超过 maxSum (5 4 = 9)，因此请跳过它。
  • 结果是 2。

• 输入 2: 禁止 = [1, 2, 3, 4, 5, 6, 7], n = 8, maxSum = 1

  • 从 1 到 7 的所有号码均被禁止，因此无法选择有效号码。
  • 结果是 0。

• 输入 3： 禁止 = [11]，n = 7，maxSum = 50

  • 唯一被禁止的号码是 11，它超出了 1 到 7 的范围。
  • 我们可以选择从1到7的所有数字，它们的总和是28，小于maxSum。
  • 结果是 7。

该解决方案可以在给定的约束条件下有效地处理问题。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是从范围 I 中选择的最大整数数的详细内容。更多信息请关注PHP中文网其他相关文章！