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 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告