袋中球的最小數量

1760。袋子中球的最小數量

難度：中

主題：數組，二分查找

給定一個整數數組 nums，其中第 i ^個 袋包含 nums[i] 個球。您還會獲得一個整數 maxOperations。

您最多可以執行以下操作 maxOperations 次：

• 取出任一包球，將其分成兩個新袋，其中球的數量為正個。
  • 例如，一袋 5 球可以變成兩袋新的 1 球和 4 球，或兩袋新的 2 球和 3 球。

你的處罰是袋中最大個球的數量。您希望將手術後的懲罰降到最低。

執行操作後回傳可能的最小懲罰。

範例1：

• 輸入： nums = [9], maxOperations = 2
• 輸出： 3
• 說明：
  • 將裝有 9 個球的袋子分成尺寸為 6 和 3 的兩個袋子。 [9] -> [6,3].
  • 將裝有 6 個球的袋子分成尺寸為 3 和 3 的兩個袋子。 [6,3] -> [3,3,3].
  • 球數最多的袋子有 3 個球，所以你的罰分是 3，你應該回傳 3。

範例2：

• 輸入： nums = [2,4,8,2], maxOperations = 4
• 輸出： 2
• 說明：
  • 將裝有 8 個球的袋子分成尺寸為 4 和 4 的兩個袋子。 [2,4,8,2] -> [2,4,4,4,2].
  • 將裝有 4 個球的袋子分成尺寸為 2 和 2 的兩個袋子。 [2,4,4,4,2] -> [2,2,2,4,4,2].
  • 將裝有 4 個球的袋子分成尺寸為 2 和 2 的兩個袋子。 [2,2,2,4,4,2] -> [2,2,2,2,2,4,2].
  • 將裝有 4 個球的袋子分成尺寸為 2 和 2 的兩個袋子。 [2,2,2,2,2,4,2] -> [2,2,2,2,2,2,2,2].
  • 球數最多的袋子有 2 個球，所以你的罰分是 2，你應該回傳 2。

約束：

• 1 5
• 1 9

提示：

1. 如果我們知道袋子的最大尺寸，那麼我們可以改變問題，你可以製作的袋子的最小數量是多少
2. 請注意，隨著最大尺寸的增加，最小袋子數量會減少，因此我們可以對最大尺寸進行二分搜尋

解：

我們可以使用二分搜尋來找出可能的最小懲罰。關鍵的見解是，如果我們可以確定給定的懲罰是否可以實現，我們可以使用二分搜尋縮小搜尋範圍。

解決步驟：

1. 二分搜尋設定:

   • 最低罰分為1（全部球均分入單球袋）。
   • 最大懲罰是nums陣列中最大的數字。

2. 可行性檢查：

   • 對於給定的懲罰中位數，檢查是否可以透過最多 maxOperations 次分割來實現它。
   • 為此，對於每個袋子尺寸（以 nums 為單位），計算使所有袋子具有中間球或更少的球所需的分割數。如果總 split 超過 maxOperations，則懲罰 mid 不可行。

3. 迭代:

   • 根據懲罰中位數是否可行，使用二分搜尋調整範圍[低，高]。

讓我們用 PHP 實作這個解：1760。袋中球的最低數量

<?php /**
 * @param Integer[] $nums
 * @param Integer $maxOperations
 * @return Integer
 */
function minimumSize($nums, $maxOperations) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Helper function to check if a penalty is feasible
 *
 * @param $nums
 * @param $maxOperations
 * @param $penalty
 * @return bool
 */
function canAchievePenalty($nums, $maxOperations, $penalty) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
$nums = [9];
$maxOperations = 2;
echo minimumSize($nums, $maxOperations); // Output: 3

// Example 2
$nums = [2, 4, 8, 2];
$maxOperations = 4;
echo minimumSize($nums, $maxOperations); // Output: 2
?>

解釋：

1. 二分查找:

   • 搜尋空間介於 1 和 nums 陣列中的最大數字之間。
   • 中點mid代表我們目前測試的懲罰。

2. 可行性檢查（可以實現懲罰）：

   • 對於每個袋子，計算所需的分割數，以確保所有袋子的中球或更少：
     • ceil(balls / mid) - 1 給予所需的分割數。
   • 如果總 split 超過 maxOperations，則懲罰不可行。

3. 調整搜尋空間:

   • 如果懲罰可行，則降低上限（高=中）。
   • 如果不是，則增加下限（低 = 中 1）。

4. 結果：

   • 當循環退出時，low包含最小的可行懲罰。

複雜：

• 時間複雜度：O(n .log(max(nums)))
  • 二分搜尋的運行時間為O(log(max(nums)))，每個中點的可行性檢查需要O(n ).
• 空間複雜度：O(1)，因為我們只使用恆定的額外空間。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是袋中球的最小數量的詳細內容。更多資訊請關注PHP中文網其他相關文章！