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

輸出

Arnab Chakraborty

更新於：2020年11月25日

138 次瀏覽

開啟你的職業生涯

透過完成課程獲得認證

開始學習