Pythonで配列からk番目に欠落している正の整数を見つける方法

問題の概要

厳密に増加する正の整数が昇順に並んだ配列 nums と、整数 k が与えられます。このとき、配列に含まれていない正の整数の中から k 番目のものを求めるのが目的です。

例として、nums = [1,2,4,8,12]、k = 6 の場合を考えてみましょう。この配列に存在しない数は [3,5,6,7,9,10,11] であり、その中で 6 番目に当たるのは 10 です。したがって、出力は 10 となります。

解法のアプローチ

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

• 配列 nums の要素をセット（set）に変換し、要素の存在判定を高速化します。
• カウンタ count を 0、探索対象の数 num を 1 で初期化します。
• count が k 未満である間、以下を繰り返します。
  • num がセットに存在しない場合、count を 1 増やします。
  • count が k と等しくなった時点で、num を答えとして返します。
  • num を 1 増やして次の候補へ進みます。
• ループを抜けた場合は num をそのまま返します。

Pythonでの実装例

以下のコードは、上記のアルゴリズムを実装したものです。

def solve(nums, k):
    nums = set(nums)
    count = 0
    num = 1
    while count < k:
        if num not in nums:
            count += 1
        if count == k:
            return num
        num += 1
    return num

nums = [1,2,4,8,12]
k = 6
print(solve(nums, k))

入力

[1,2,4,8,12], 6

出力

10

計算量について

この解法では、探索する num は最悪でも「配列の最大値 + k」程度までしか進まないため、時間計算量は O(n + k) です。また、セットへの変換に伴い空間計算量は O(n) となります。二分探索を用いれば O(log n) への高速化も可能ですが、コードのシンプルさと分かりやすさを重視するなら、この線形探索のアプローチが適しています。