【Python】ソート済みリストからk番目に欠けている数を効率的に求める方法

ソートされた重複のない整数リスト nums と整数 k が与えられたとき、リストの最初の要素を基準にして、k番目（0始まりのインデックス）に相当する欠落した数を見つける問題を考えてみましょう。

問題の例

例えば、nums = [5,6,8,10,11]、k = 1 という入力の場合を確認します。このリストには「7」と「9」という2つの数が欠けています。7がインデックス0（1番目）の欠落数、9がインデックス1（2番目）の欠落数に対応するため、k = 1 のときの出力は 9 となります。

解決のためのアプローチ

この問題は、隣り合う要素同士の差に注目することで解けます。各間隔にいくつの数が欠けているかを順番に数え、k番目の欠落数がどの間隔に含まれるかを特定します。手順は以下の通りです。

• i を 1 から nums のサイズ未満まで繰り返します。

  • diff := nums[i] − nums[i−1] − 1（隣接要素間に欠けている数の個数）

  • k ≥ diff の場合：
    k := k − diff とし、次の間隔へ進む

  • それ以外の場合：
    nums[i−1] + k + 1 を返す

• ループが完了しても見つからない場合は、リスト末尾より先の値として nums[−1] + k + 1 を返します。

実装例

以下のコードで実際の動作を確認してみましょう。

class Solution:
    def solve(self, nums, k):
        for i in range(1, len(nums)):
            diff = nums[i] - nums[i - 1] - 1
            if k >= diff:
                k -= diff
            else:
                return nums[i - 1] + k + 1
        return nums[-1] + k + 1

ob = Solution()
nums = [5,6,8,10,11]
k = 1
print(ob.solve(nums, k))

入力

[5,6,8,10,11], 1

出力

9

処理の流れを詳しく見る

上記の例では、まず 5 と 6 の差分から欠落数 0 個を引きます（k は 1 のまま）。次に 6 と 8 の間隔には 7 が欠けているため diff = 1 となり、k を 1 減らして 0 にします。さらに 8 と 10 の間隔では diff = 1 ですが k = 0 < 1 であるため、この時点で 8 + 0 + 1 = 9 が答えとして返されます。

計算量について

この線形探索ベースのアプローチでは、時間計算量は O(n)、空間計算量は O(1) となります。リストのサイズが非常に大きく、かつ二分探索を用いた最適化が必要な場合は、累積的な欠落数をもとに O(log n) で解く方法も検討できます。ただし、多くの実用的なケースでは上記のシンプルな実装で十分に高速に動作します。