Python程序：查找k次递增后出现次数最多的数字

假设我们有一个名为nums的数字列表和另一个值k。让我们考虑一个操作，其中我们将某个元素增加一。我们最多可以执行k次，我们必须找到可以获得的出现频率最高的数字的值。如果有多个解决方案，请选择最小的数字。

因此，如果输入类似于nums = [1, 0, 0, 0, 8, 8, 8, 8] k = 8，则输出将为8，因为我们可以将1增加7次以得到8，并将任何0增加到1，所以我们得到[8, 1, 0, 0, 8, 8, 8, 8]。所以结果是8。

为了解决这个问题，我们将遵循以下步骤

• 对列表nums进行排序
• low := 0, high := 0
• dist := 0, best := 0
• ret := -1
• 当 high < nums 的大小 时，执行
  • 如果 high > 0 且 nums[high] 与 nums[high - 1] 不相同，则
    • dist := dist +(high - low) *(nums[high] - nums[high - 1])
  • high := high + 1
  • 当 dist > k 时，执行
    • dist := dist - nums[high - 1] - nums[low]
    • low := low + 1
  • 如果 high - low > best，则
    • best := high - low
    • ret := nums[high - 1]
  • 返回 ret

让我们看看下面的实现以获得更好的理解

示例代码

在线演示

class Solution:
   def solve(self, nums, k):
      nums.sort()
      low, high = 0, 0
      dist = 0
      best = 0
      ret = -1
      while high < len(nums):
         if high > 0 and nums[high] != nums[high - 1]:
            dist += (high - low) * (nums[high] - nums[high - 1])
            high += 1
            while dist > k:
               dist -= nums[high - 1] - nums[low]
               low += 1
               if high - low > best:
                  best = high - low
                  ret = nums[high - 1]
               return ret

ob = Solution()
nums = [1, 0, 0, 0, 8, 8, 8, 8]
k = 8
print(ob.solve(nums, k))

输入

[1, 0, 0, 0, 8, 8, 8, 8], 8

输出

8

Arnab Chakraborty

更新于：2020年11月25日

138 次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习