從範圍 I 中選擇的最大整數數-php教程-PHP中文網

Maximum Number of Integers to Choose From a Range 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。

約束：

提示：

將小於 n 的禁用號碼保留在一組中。
循環從1到n的數字，如果該數字沒有被禁止，則使用它。
在未被禁止的情況下不斷相加，且它們的總和小於k。

解：

我們可以使用貪心方法，迭代從 1 到 n 的數字，跳過禁止的數字，並繼續將有效數字（不在禁止數組中的數字）添加到運行總和中，直到達到 maxSum。

以下是逐步解決方案：

步驟：

將禁止數組轉換為集合以進行快速查找：使用 array_flip() 可以將禁止數組轉換為集合以進行 O(1) 平均時間複雜度查找。
從 1 迭代到 n： 檢查每個數字，如果它不在禁止的集合中，並且如果相加沒有超過 maxSum，則將其添加到總和中並增加計數。
一旦添加下一個數字超過 maxSum 就停止：由於目標是最大化所選整數的數量而不超過總和，因此這種貪心方法確保我們首先獲取最小的可用數字。

方法：

排除停用號碼：我們將追蹤集合（或關聯數組）中的停用號碼，以便快速找到。
貪婪選擇： 開始按升序選擇從 1 到 n 的數字，因為這將使我們能夠最大化所選整數的數量。每次我們選擇數字時，我們都會將其加到總和中並檢查它是否超過 maxSum。如果是這樣，請停止。
效率考慮因素：由於我們迭代從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
?>

登入後複製

解釋：

將停用陣列轉換為設定：

我們使用 array_flip($banned) 從被禁止的陣列中建立一個集合，這允許 O(1) 查找來檢查某個數字是否被禁止。
從 1 迭代到 n：

我們迭代從 1 到 n 的數字。對於每個數字：
- 如果號碼不在禁止集中（使用 isset($bannedSet[$i]) 檢查），
- 如果將數字加到總和中不超過 maxSum，
- 我們包含該數字並更新總和和計數。
回傳計數：

循環結束後，我們傳回所選整數的數量 ($count)。
$bannedSet = array_flip($banned);：這會將禁止清單轉換為集合（關聯陣列）以進行快速尋找。
for ($i = 1; $i ：我們迭代從 1 到 n 的所有整數。
if (isset($bannedSet[$i])) { 繼續; }：檢查目前號碼是否在禁止集中。如果是，我們就跳過它。
if ($sum $i > $maxSum) {break; }：如果添加當前數字超過 maxSum，我們將停止該過程。
$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。