Pythonで配列内の最初に欠けている正の整数を求めるアルゴリズム

問題の概要

ソートされていない整数型配列が1つ与えられたとき、その中に存在しない最小の正の整数を見つけることを考えます。例えば、配列が [4, -3, 1, -1] の場合、1は存在しますが2が存在しないため、答えは 2 となります。

この問題は、配列を「インデックスと値を対応させる」ことで O(n) の時間計算量で解くことができます。以下の手順に従って解いていきましょう。

解法のアプローチ

• 変数 i を 0 に初期化し、配列 nums の先頭に 0 を挿入して更新します(インデックスと値を一致させるため)。
• i を 0 から nums の長さまでループさせます。
  • 条件「nums[i] >= 0 かつ nums[i] < len(nums) かつ nums[nums[i]] != nums[i]」が成り立つ間、以下を繰り返します。
    • nums[nums[i]] と nums[i] の値をスワップし、各値を本来あるべき位置へ移動させます。
• num を 1 に初期化します。
• i を 1 から nums の長さまでループさせます。
  • num == nums[i] であれば、num を 1 増やします。
• 最後に num を返します。これが最初に欠けている正の整数です。

実装例

それでは、実際のコードを見て理解を深めましょう。

class Solution(object):
   def firstMissingPositive(self, nums):
   i = 0
   nums = [0] + nums
   for i in range(len(nums)):
      while nums[i]>=0 and nums[i]<len(nums) and nums[nums[i]]!=nums[i]:
         nums[nums[i]],nums[i] = nums[i],nums[nums[i]]
      num = 1
      for i in range(1,len(nums)):
         if num == nums[i]:
            num+=1
      return num

ob = Solution()
print(ob.firstMissingPositive([4,-3,1,-1]))

入力

[4,-3,1,-1]

出力

2

アルゴリズムのポイント

この手法の核心は、各要素をその値に対応するインデックスの位置へ移動させることです。先頭に 0 を追加することで、「値 v はインデックス v に置かれるべき」という対応関係が成立します。スワップ処理により正の整数を適切な位置に配置した後、先頭から順に確認していき、初めて連続が途切れる位置の値が答えとなります。

負の数や配列の範囲外の値は無視されるため、結果として欠けている最小の正の整数が正しく求まります。時間計算量は O(n)、空間計算量は O(1)(入力配列をそのまま利用する場合)と非常に効率的です。