Pythonで最大k回の操作後に実現できる要素の最大頻度を求めるプログラム

問題の概要

配列 nums と整数 k が与えられます。1回の操作ごとに、nums 内の任意のインデックスを1つ選び、その位置の要素の値を1だけ増やすことができます。操作は最大 k 回まで行えるとき、最終的にある1つの要素が持ち得る最大の出現頻度（同じ値の個数）を求めてください。

たとえば、入力が nums = [8,3,6]、k = 9 の場合、出力は 3 になります。要素 3 を5回、要素 6 を2回増やすことで配列を [8,8,8] にでき、合計7回の操作で頻度3を達成できるためです。

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

この問題は、配列をあらかじめソートしておき、スライディングウィンドウ（2つのポインタ）を使うことで効率的に解けます。ウィンドウ内のすべての要素を右端の値に揃えるために必要な操作回数を管理しながら、予算 k の範囲で可能な限り幅の広いウィンドウを維持するのがポイントです。手順は以下のとおりです。

• リスト nums を昇順にソートします。
• 左端 left = 0、右端 right = 1 で初期化します。
• right が配列の長さに達するまで、以下を繰り返します。
  • k -= (nums[right] - nums[right-1]) * (right - left)：ウィンドウ内の全要素を nums[right] に揃えるためのコストを差し引きます。
  • k が負になった場合は予算超過なので、k += nums[right] - nums[left] でコストを巻き戻し、left を1つ進めてウィンドウを縮めます。
  • right を1つ進めてウィンドウを広げます。
• ループ終了後、right - left を返します。これが求める最大頻度です。

実装例

理解を深めるために、以下のPython実装を見てみましょう。

def solve(nums, k):
   nums.sort()
   left = 0
   right = 1

   while right < len(nums):
      k -= (nums[right] - nums[right-1]) * (right - left)

      if k < 0:
         k += nums[right] - nums[left]
         left += 1

      right += 1

   return right - left

nums = [8,3,6]
k = 9
print(solve(nums, k))

入力

[8,3,6], 9

出力

3

計算量

ソートに O(n log n)、その後の2ポインタによる走査に O(n) かかるため、全体の時間計算量は O(n log n) です。追加のデータ構造が不要なため、空間計算量もほぼ O(1) で抑えられる、非常に効率的な解法といえます。