Pythonで最大k回の増加操作後に最も頻出する数を求めるプログラム

問題の概要

数値のリスト nums と整数 k が与えられます。「リスト内の任意の要素を1つ選び、その値を1だけ増やす」という操作を最大 k 回まで行えるとき、操作後に最も多く出現することになる数の値を求めてください。候補が複数ある場合は、そのうち最も小さい値を返します。

たとえば nums = [1, 0, 0, 0, 8, 8, 8, 8]、k = 8 の入力を考えてみます。値 1 を7回増やして 8 にすれば、残りの1回で 0 のいずれかを 1 にできます。結果は [8, 1, 0, 0, 8, 8, 8, 8] となり、8 が5個並ぶため、答えは 8 になります。

アプローチ：スライディングウィンドウ

この問題は、リストをソートしたうえでスライディングウィンドウ(二ポインタ法)を使うと効率的に解けます。ウィンドウ [low, high) は、含まれる各要素をウィンドウ内の最大値 nums[high - 1] まで引き上げるのに必要な増分の合計が k 以内に収まる範囲を表します。

具体的な手順は次のとおりです。

• リスト nums をソートします。
• low := 0、high := 0 で初期化します。
• dist := 0(ウィンドウ内の要素を右端の値に揃えるために必要な増分の合計)、best := 0(これまでに見つかった最大の出現数)、ret := -1(答えとなる値)を用意します。
• high がリストの長さ未満である間、次を繰り返します。
  • high > 0 かつ nums[high] != nums[high - 1] のとき、dist += (high - low) * (nums[high] - nums[high - 1]) で必要コストを更新します。
  • high を1つ進めます。
  • dist > k の間、dist -= nums[high - 1] - nums[low] として low を1つ進め、予算オーバーになった分だけウィンドウを左側から縮めます。
  • high - low > best なら、best := high - low、ret := nums[high - 1] として答えを更新します。
• 最後に ret を返します。

リストは昇順にソートされているため、出現数が同じ候補が複数あっても、先に記録されるのはより小さい値を持つウィンドウです。したがって「同数なら最小の値を選ぶ」という条件も自然に満たされます。

実装例(Python)

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

計算量について

ソートに O(n log n)、その後のウィンドウ処理は左右のポインタが各要素を高々1回ずつ通過するだけなので O(n) で済みます。全体の計算量は O(n log n) となり、全ペアを総当たりで調べる O(n²) の素朴な手法と比べて、大きな入力でも高速に動作します。追加のメモリも定数程度で済む点が魅力です。