從範圍 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中文網其他相關文章！