Pythonで「x以上の要素がちょうどx個」ある特別な配列のxを求めるプログラム

すべての要素が 0 または正の整数である配列 nums があるとします。この配列は、ある数値 x が存在して、nums の中に「x 以上の要素」がちょうど x 個含まれるとき、特別な配列(special array)と呼ばれます。ポイントは、x が必ずしも nums の要素である必要はないという点です。配列が特別な配列であればその x を求め、そうでなければ -1 を返します。

たとえば、入力が nums = [4, 6, 7, 7, 1, 0] の場合を考えてみましょう。4 以上の要素は 4, 6, 7, 7 の 4 個あるため、出力は 4 となります。

解き方のアプローチ

この問題は、次の手順で解くことができます。

• i を 0 から nums の最大値まで 1 ずつ増やしながら調べる
• 各 i について、nums 内の i 以上の要素の個数 count を数える
• count が i と一致すれば、その i が答えなので返す
• すべての候補を調べても見つからなければ -1 を返す

Pythonでの実装例

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

def solve(nums):
    for i in range(max(nums) + 1):
        count = 0
        for j in nums:
            if j >= i:
                count += 1
        if count == i:
            return i
    return -1

nums = [4, 6, 7, 7, 1, 0]
print(solve(nums))

入力

[4, 6, 7, 7, 1, 0]

出力

4

計算量の改善

上記の素朴な実装では、候補となる x の範囲(最大で max(nums) + 1 通り)ごとに配列全体を走査するため、時間計算量は O(n²) になります(n は配列の長さ)。配列をあらかじめ昇順にソートしておけば、二分探索(bisect モジュール)を使って「x 以上の要素の個数」を効率よく求められるため、計算量を O(n log n) まで抑えられます。

import bisect

def solve_fast(nums):
    nums.sort()
    n = len(nums)
    lo, hi = 0, n
    while lo <= hi:
        mid = (lo + hi) // 2
        cnt = n - bisect.bisect_left(nums, mid)
        if cnt == mid:
            return mid
        elif cnt > mid:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

nums = [4, 6, 7, 7, 1, 0]
print(solve_fast(nums))  # 出力: 4

このように、まずシンプルな全探索で問題の構造を理解し、その後ソートと二分探索を組み合わせることで、より大規模な入力にも対応できる実装へと改善できます。