Pythonで「値がk以上の要素がちょうどk個」成立するkを見つける方法

非負の整数のみを含むリスト nums が与えられます。この中から、「k 以上の値を持つ要素がちょうど k 個存在する」ような整数 k を見つけて返すことを考えます。条件を満たす k が存在しない場合は -1 を返します。

たとえば、入力が nums = [6, 4, 0, 8, 2, 9] の場合を考えてみましょう。4 以上の値を持つ要素は [6, 4, 8, 9] のちょうど 4 個であるため、答えは 4 になります。

解法の考え方

この問題は、リストを降順にソートすることで効率的に解けます。降順ソート後のリストでは、インデックス i より前にある要素はすべて nums[i - 1] 以上の値を持つため、「先頭から i 個の要素が i 以上になっているか」という判定が容易になります。

アルゴリズムの手順

• リスト nums を降順にソートする
• i を 1 からリストの長さ - 1 まで繰り返し処理する
  • i > nums[i - 1] の場合：それ以降に条件を満たす値は存在しないため、ループを抜ける
  • そうでなく、i > nums[i] の場合：「i 以上の要素がちょうど i 個」を満たすので、i を返す
• ループが完了しても見つからなければ、-1 を返す

実装例

実際のPythonコードは次のようになります。

def solve(nums):
    nums.sort(reverse=True)
    for i in range(1, len(nums)):
        if i > nums[i - 1]:
            break
        elif i > nums[i]:
            return i
    return -1

nums = [6, 4, 0, 8, 2, 9]
print(solve(nums))

入力

[6, 4, 0, 8, 2, 9]

出力

4

計算量について

ソートに O(n log n)、ソート後のリスト走査に O(n) の時間がかかるため、全体の時間計算量は O(n log n) です。追加のデータ構造を必要としないシンプルな解法であり、実用性の高いアプローチといえます。