PythonでK個の要素を削除した後に残る一意な整数の最小数を求める方法

問題の概要

整数のみが格納された配列 nums と、削除する個数 k が与えられたとします。このとき、ちょうど k 個の要素を削除した後に残る「一意な(ユニークな)整数」の種類数を最小化することを考えます。

例として、nums = [5,4,2,2,4,4,3]、k = 3 の場合を見てみましょう。まず 5 と 3 を削除し、さらに 2 または 4 のどちらか一方を1つ削除すると、残るのは 2 と 4 のみになります。したがって、この場合の出力は 2 となります。

解法のアプローチ

この問題は貪欲法(グリーディ法)で効率よく解けます。ポイントは、「出現回数が最も少ない要素から順に削除する」ということです。出現回数の少ない要素を優先的に削除すれば、限られた削除回数でより多くの種類を丸ごと消せるため、結果として残る一意な整数の数を最小にできます。

具体的な手順は以下の通りです。

• 各整数の出現回数を記録するための辞書(dictionary)を新しく作成します。
• 配列内の各要素について、辞書に存在しなければ出現回数を 1 とし、すでに存在すればカウントを +1 します。
• count を辞書のサイズ(= 一意な整数の種類数)で初期化します。
• すべての出現回数を昇順にソートし、小さい方から順に以下を繰り返します。
  • k からその出現回数を引きます。
  • k が負になった場合は、これ以上その種類を完全には削除できないため、現在の count を返します。
  • そうでなければ、その種類を完全に削除できたことになるので、count を -1 します。
• ループが完了したら、最終的な count を返します。

実装例

それでは、実際のPythonコードを見てみましょう。

def solve(nums, k):
    dictionary={}
    for num in nums:
        if num not in dictionary:
            dictionary[num]=1
        else:
            dictionary[num]+=1
    count=len(dictionary)
    for frequency in sorted(dictionary.values()):
        k-=frequency
        if(k<0):
            return count
        else:
            count-=1
    return count

nums = [5,4,2,2,4,4,3]
k = 3
print(solve(nums, k))

入力

[5,4,2,2,4,4,3], 3

出力

2

計算量の目安

• 時間計算量: O(n log n) ― 出現回数のソートが支配的です(n は配列の長さ)。
• 空間計算量: O(n) ― 各一意な整数の出現回数を辞書に保持するためです。

このように、出現頻度の低い要素から優先的に削除するシンプルな発想だけで、一意な整数の最小数を効率的に求めることができます。