Python程式：查詢k次操作後最小可能最大值

假設我們有一個名為nums的數字列表和另一個值k。現在讓我們考慮一個操作，我們可以從列表中的任何元素中減去1。我們可以執行此操作k次。我們必須找到k次此類操作後列表中最小可能的最大值。

因此，如果輸入類似於nums = [3, 4, 6, 5] k = 6，則輸出將為3，因為我們可以將4減少一次，6減少三次，5減少兩次以得到[3,3,3,3]。

為了解決這個問題，我們將遵循以下步驟：

  • 按降序排列數字
  • i := 0
  • curr := nums[0]
  • 當k > 0時，執行：
    • 當i < nums的大小且nums[i]與curr相同時，執行：
      • i := i + 1
    • 如果k >= i，則：
      • k := k - i
      • curr := curr - 1
    • 否則：
      • 返回curr
  • 返回curr

讓我們看下面的實現來更好地理解。

示例

線上演示

class Solution:
   def solve(self, nums, k):
      nums.sort(reverse=True)
      i = 0
      curr = nums[0]
      while k > 0:
         while i < len(nums) and nums[i] == curr:
            i += 1
         if k >= i:
            k -= i
            curr -= 1
         else:
            return curr
      return curr

ob = Solution()
nums = [3, 4, 6, 5]
k = 6
print(ob.solve(nums, k))

輸入

[3, 4, 6, 5], 6

輸出

3

更新於：2020年11月26日

875 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告