First Missing Positive
整数の未ソート配列 nums が与えられます。nums に含まれていない最小の正の整数（1以上）を返してください。配列には、負の数、ゼロ、重複した値、配列の長さよりはるかに大きい値が含まれる場合があります。
関数
- numsinteger-array
- 未ソートの整数。重複する場合があり、負の値、ゼロ、または非常に大きな値である可能性があります
- 戻り値integer
- nums に含まれていない最小の正の整数
制約
1 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109- 値は特定の順序に並んでいるわけではなく、重複する場合もあります。
例
- 入力
- nums = [5, -2, 1, 3, 2, 9]
- 出力
- 4
- 説明
- 1、2、3はすべて配列に含まれており、4は含まれていないため、答えは4です。より小さい値が欠けている場合、5と9は関係ありません。
- 入力
- nums = [4, 2, 1, 3]
- 出力
- 5
- 説明
- 配列には1から4までのすべての値が含まれているため、最初に欠けている値は5で、配列の長さより1大きい値です。
- 入力
- nums = [-1, 0, 6, 8]
- 出力
- 1
- 説明
- -1 と 0 は正の数ではなく、6 と 8 では 1 が余るので、答えは 1 です。
発展問題
追加メモリを O(1) だけ使用して、O(n) 時間で答えを見つけられますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
長さ n の配列には n 個の値が格納されます。答えは最大でどれくらいの大きさになるでしょうか？そのため、配列内のどの値を無視できますか？
答えは最大でも n+1 なので、1 から n までの値だけを考えれば十分です。どの値が現れるかを記録するには、n 個のフラグの表があれば足ります。配列自体にはちょうど n 個のスロットがあります。それをその表として使えるでしょうか？
値
vはインデックスv-1に置きます。1 から n までの各値を対応する位置に移し、その位置の値に置き場所がないか、置き場所にすでに同じ値が入っている場合は、同じインデックスでの入れ替えを続けます。次に、i+1が入っていない最初のインデックスiが答えです。すべての位置が正しければ n+1 です。
解説
ソートには O(n log n) の時間がかかり、ハッシュセットには O(n) の追加メモリが必要です。上限を使えば、どちらも不要です。n 個の値でカバーできるのは、1 から n+1 までの数のうち最大 n 個なので、答えは最大でも n+1 です。重要なのは 1 から n までの値だけであり、それらを記録するための n 個のスロットが配列にあるので、追加メモリは O(1) に抑えられます。
各候補を全件走査で試してみましょう
正しいが、最大のテストでは終わらない
考え方
候補の1、2、3、...を順番にテストします。それぞれについて配列全体を調べ、走査で見つからなかった最初の候補を返します。この上限により、n+1を超えてテストすることはありません。
配列に1からnまでの値が入っている場合、各候補は平均して途中まで調べたところで見つかるため、n = 10^4では約 n²/2 = 5 × 10^7 回の比較が必要です。
アルゴリズム
candidateを1に設定します。numsを走査し、candidateと等しい要素を最初に見つけた時点で停止します。- 一致する要素がなければ、
candidateを返します。 - それ以外の場合は、
candidateに1を加えて、再度走査します。n+1を超えることはありません。
def firstMissingPositive(nums):
n = len(nums)
# n values cannot cover all of 1..n+1, so one of these candidates is missing
for candidate in range(1, n + 2):
found = False
for num in nums:
if num == candidate:
found = True
break
if not found:
return candidateフラグ配列内で1からnまでの値に印を付ける
考え方
答えは最大でも n+1 なので、1 未満または n より大きい値はスキップします。長さ n+1 のブール配列 present に残りの値を記録するため、10^9 のような値が保存されることはありません。フラグが false である 1 から n までの最初の v を返し、すべてのフラグが設定されている場合は n+1 を返します。
最初の例では n = 6 です。1、2、3、5 のフラグが設定され、-2 と 9 はスキップされ、最初に設定されていないフラグは 4 です。2 回の線形走査で O(n) 時間となり、フラグには O(n) のメモリが必要です。
アルゴリズム
presentを作成し、n+1個のフラグをfalseに設定します。nums内の各値vについて、1 ≤ v ≤ nの場合、present[v]をtrueに設定します。- フラグがfalseである、1からnまでの最初の
vを返します。 - そのような値がなければ、n+1を返します。
def firstMissingPositive(nums):
n = len(nums)
# present[v] says whether v is in nums; only 1..n can matter
present = [False] * (n + 1)
for num in nums:
if 1 <= num <= n:
present[num] = True
for v in range(1, n + 1):
if not present[v]:
return v
return n + 1各値をそれぞれ別のスロットに配置する
考え方
値 v はインデックス v-1 に置きます。1 から n までのすべての値が本来の位置にあるとき、i+1 が置かれていない最初のインデックス i が答えを示します。
各インデックスで、値が 1 から n の範囲内にあり、その値の本来の位置にまだ置かれていない場合は、値を本来の位置へ移します。戻ってきた値も移動が必要なことがあります。i ではなく本来の位置を確認することで、重複を止められます。[1, 1] では、2つ目の 1 はインデックス 0 に 1 があるのを確認して、そのまま残ります。
最初の例では、インデックス 0 が 5 を本来の位置に移し、次に戻ってきた 2 を移します。その後、1 と 3 が本来の位置に移り、[1, 2, 3, -2, 5, 9] が残ります。インデックス 3 が最初の誤った位置なので、答えは 4 です。
各スワップで1つの値が確実に本来の位置に収まるため、内側のループで行うスワップの合計は最大 n 回です。したがって、時間計算量は O(n)、メモリ使用量は O(1) です。ただし、R では変更するベクトルをコピーします。
アルゴリズム
- 0 から n-1 までの各インデックス
iについて: 1 ≤ nums[i] ≤ nかつnums[nums[i]-1] ≠ nums[i]の間、nums[i]とnums[nums[i]-1]を入れ替える。- 配置処理の後、
nums[i] ≠ i+1となる最初のインデックスiを見つけ、i+1を返す。 - すべての位置に対応する値が入っている場合は、n+1 を返す。
def firstMissingPositive(nums):
n = len(nums)
for i in range(n):
# Keep swapping until slot i holds a value that has no slot or is already home
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
home = nums[i] - 1
nums[i], nums[home] = nums[home], nums[i]
# The first slot that does not hold its own value names the answer
for i in range(n):
if nums[i] != i + 1:
return i + 1
return n + 1
落とし穴と境界ケース
- 値があるべき位置にあるかではなく、
nums[i] == i+1になるまで交換を続ける。[1, 1]の場合、2つの1が無限に交換される。 whileではなくifで交換する。最初の例では、インデックス4から戻ってきた2がインデックス1に到達せず、4ではなく2を返してしまう。nums[i] = nums[nums[i]-1]と書いたあと、再びnums[i]を使ってインデックスを指定する。これでは変更後の値であるべき位置のインデックスを読み取ってしまう。先に、値があるべき位置のインデックスを保存する。- 範囲チェックを省略すると、0、-2、10^9によって配列の範囲外のインデックスが指定される。
- すべての要素が正しい位置にあるときにnを返す。
[4, 2, 1, 3]の場合、答えは5。
よくある質問3
First Missing Positive の時間計算量は何ですか？
配置方案的时间复杂度为 O(n)，额外空间复杂度为 O(1)。while 循环位于 for 循环内部，但每次交换都会将一个值放到其最终索引处，因此整个过程最多进行 n 次交换。使用标记数组的版本时间复杂度为 O(n)、空间复杂度为 O(n)，而对每个候选项进行扫描的时间复杂度为 O(n²)。
答えが n+1 より大きくなることがないのはなぜですか？
1 から n+1 までの数は n+1 個の異なる値であり、長さ n の配列に格納できる異なる値は最大 n 個なので、そのうちの 1 つが欠けています。配列に 1 から n までのすべての値が格納されている場合に限り、答えは n+1 です。
インプレースの解決策は入力配列を変更しますか？
はい、値の順序が入れ替わります。呼び出し元が元の順序を必要とする場合は、まず配列をコピーします。その場合、追加のメモリ使用量は再び O(n) になります。別のインプレース手法では、1 から n の範囲外にあるすべての値を n+1 に置き換え、その後 nums[v-1] を負の値にすることで、v が存在することを記録します。この方法も配列を変更します。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def firstMissingPositive(nums):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
nums = [5, -2, 1, 3, 2, 9]
期待される出力
4