方針１で解いた場合、Time Limit Exceededで失敗しました。
二分探索を用いた方針2で解いこうとしましたが、失敗しました。おそらく二分探索の実装が間違っています。
線形探索を用いた方針3で解き、成功しました。
追記に、二分探索で成功したということを書いています。
問題
こちらから挑戦することができます。
https://leetcode.com/problems/first-missing-positive/
ソートされていない整数配列numsが与えられています。欠けている最小の正の整数を返してください。
O(n)時間で実行され、一定の空間を使用するアルゴリズムを実装する必要があります。
（例と制約についてはリンク先のページにあるので省略します。）
方針1
numsの最大の数を探す。
最大の数が正の整数でないなら、1を返す。
最大の数が正の数ならば以下を行う。
1から最大の数+1までの数を要素とした集合を作る。…①
numsのうち正である数だけを採った集合を作る。…②
②のうち①に含まれないもののうち最小の数を採り、それを返す。
提出したコード
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
#ソートしても問題ない場合、何も考えずにソートします。
nums.sort()
# numsの最大の数
max_nums = max(nums)
if max_nums <= 0: #0は正の整数に含まれないので、0以下を条件にします。
return 1
else: # max_numsが正の整数の場合
# candidates: 返される数の候補たち。1からmax_nums + 1まで。
candidates = {i for i in range(1, max_nums + 2)}
# pos_nums: numsのうち正である数
pos_nums = {x for x in nums if x >= 1}
# 候補の中の最小の数を返す。
return min(candidates - pos_nums)
結果：Time Limit Exceeded
反省1
たとえpos_numsの要素が1個だけでも、それが100000000とかであった場合、candidatesに対して100000000個の要素を作らなければならないです。
それが原因してTime Limit Exceededを起こしたものと思われます。
方針2
numsをソートする。
numsの中の正の数だけを採った配列pos_numsを用意する。
pos_numsの最大の数(max_pos_num)、最小の数（min_pos_num）を調べる。それぞれ、配列の最も右の数、最も左の数である。
min_pos_numが2以上ならば、1を返す。
min_pos_numが1ならば、以下を考える。
仮に、pos_numsが、正の数が欠けていない配列ならば、sum(pos_nums) == (1 + len(pos_nums)) * len(pos_nums) / 2が成り立つ。その場合には、max_pos_num + 1を返す。
仮に、pos_numsが、正の数が欠けていない配列ならば、その位置と内容の間には pos_nums[i] == i + 1 の関係が成り立つ。
内容 = 位置 + 1の関係が成り立たない最も左の場所を探し、その場所の直前の左の数に1を加えたものを、答えとして返す。
探索には二分探索を用いる。
提出したコード2
import math
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
# ソートしても問題ない場合、何も考えずにソートします。
# もともとの配列に数字が重複している場合があるので、それをsetを使って削除します。
nums = sorted(list(set(nums)))
# numsの最大の数
max_num = max(nums)
if max_num <= 0: #0は正の整数に含まれないので、0以下を条件にします。
return 1
# pos_nums: numsのうち正である数
pos_nums = [x for x in nums if x >= 1]
# pos_numsの最大の数(max_pos_num)、最小の数（min_pos_num）を取得する。
# それぞれ、配列の最も右の数、最も左の数である。
max_pos_num = pos_nums[-1]
min_pos_num = pos_nums[0]
# min_pos_numが2以上ならば、1を返す。
if min_pos_num >= 2:
return 1
# 以下は、min_pos_numが1の場合。
# 仮に、pos_numsが、正の数が欠けていない配列ならば、
# それは初項 1，公差 1，項数 max_pos_numの等差数列である。等差数列の和の公式より、
# sum(pos_nums) == (1 + len(pos_nums)) * len(pos_nums) / 2
# が成り立つ。
# その場合には、len(pos_nums) + 1を返す。
if sum(pos_nums) == (1 + len(pos_nums)) * len(pos_nums) / 2:
return len(pos_nums) + 1
# 以下は、pos_numsが等差数列ではない場合。
# 仮に、pos_numsが、正の数がかけていない配列ならば、その位置と内容の間には
# pos_nums[i] == i + 1
# の関係が成り立つ。
# 内容 = 位置 + 1の関係が成り立たない最も左の場所を探し、
# その場所の直前の左の数に1を加えたものを、答えとして返す。
# この探索には、今回は線形探索を用いる。
#l: 二分探索の左側の端
#r: 二分探索の右側の端
#c: 二分探索の中央を示す。
l = 0
r = len(pos_nums) - 1
c = math.ceil((l + r) / 2)
while True:
# lとrが等しい時には、探索を終了する。
if l == r:
#l, r, cが示している場所は、等差数列を乱しているラインの右でもありうるし、左でもありうる。
#pos_nums[c] - pos_nums[c - 1] == 1 ならば、そのラインの左側である。
#l == 0 の場合も、そのラインの左側である。
if l == 0 or pos_nums[c] - pos_nums[c - 1] == 1:
return pos_nums[c] + 1
elif r == len(pos_nums) - 1 or pos_nums[c] - pos_nums[c - 1] != 1:
#pos_nums[c] - pos_nums[c - 1] == 1 ならば、そのラインの右側である。
return pos_nums[c - 1] + 1
return res
# pos_nums[c] == c + 1 が成り立つならば、lを現在のcより1つ右にずらす。
# そのうえでcを更新する。
if pos_nums[c] == c + 1:
l = c + 1
c = math.floor((l + r) / 2)
continue
# pos_nums[c] == c + 1 が成り立たないならば、rを現在のcより1つ左にずらす。
# そのうえでcを更新する。
else:
r = c - 1
c = math.floor((l + r) / 2)
continue
# 探索してもズレが見つからなかった場合には、-1を返す。
return -1
結果：Time Limit Exceeded
反省2
二分探索の実装が間違っていると思われます。
方針3
背伸びせずに、線形探索で探索を行います。
提出したコード3
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
# ソートしても問題ない場合、何も考えずにソートします。
# もともとの配列に数字が重複している場合があるので、それをsetを使って削除します。
nums = sorted(list(set(nums)))
# numsの最大の数
max_num = max(nums)
if max_num <= 0: #0は正の整数に含まれないので、0以下を条件にします。
return 1
# pos_nums: numsのうち正である数
pos_nums = [x for x in nums if x >= 1]
# pos_numsの最大の数(max_pos_num)、最小の数（min_pos_num）を取得する。
# それぞれ、配列の最も右の数、最も左の数である。
max_pos_num = pos_nums[-1]
min_pos_num = pos_nums[0]
# min_pos_numが2以上ならば、1を返す。
if min_pos_num >= 2:
return 1
# 以下は、min_pos_numが1の場合。
# 仮に、pos_numsが、正の数が欠けていない配列ならば、
# それは初項 1，公差 1，項数 max_pos_numの等差数列である。等差数列の和の公式より、
# sum(pos_nums) == (1 +len(pos_nums)) * len(pos_nums) / 2
# が成り立つ。
# その場合には、max_pos_num + 1を返す。
if sum(pos_nums) == (1 + len(pos_nums)) * len(pos_nums) / 2:
return len(pos_nums) + 1
# 以下は、pos_numsが等差数列ではない場合。
# 仮に、pos_numsが、正の数がかけていない配列ならば、その位置と内容の間には
# pos_nums[i] == i + 1
# の関係が成り立つ。
# 内容 = 位置 + 1の関係が成り立たない最も左の場所を探し、
# その場所の直前の左の数に1を加えたものを、答えとして返す。
# この探索には、今回は線形探索を用いる。
for i, num in enumerate(pos_nums, start = 1):
if i != num:
# その場所の直前の左の数に1を加えたもの : i - 1 + 1 == i
return i
# 探索してもズレが見つからなかった場合には、max_pos_num + 1を返す。
return max_pos_num + 1
結果：Success
反省3
解けて気持ちいいので反省は特にないです！！！！！！！
追記：二分探索に成功しました。
二分探索に失敗していた原因は、lとrの差が1の時に、lがrより大きくなったり、rがlより小さくなったりすることです。
おかしくなる条件がわかっているのでif文を用いて厳密に書いてもいいものの、ネストが深くなって将来の私にとって読めなくなるので、maxとminを使ってどうにかします。
import math
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
# ソートしても問題ない場合、何も考えずにソートします。
# もともとの配列に数字が重複している場合があるので、それをsetを使って削除します。
nums = sorted(list(set(nums)))
# numsの最大の数
max_num = max(nums)
if max_num <= 0: #0は正の整数に含まれないので、0以下を条件にします。
return 1
# pos_nums: numsのうち正である数
pos_nums = [x for x in nums if x >= 1]
# pos_numsの最大の数(max_pos_num)、最小の数（min_pos_num）を取得する。
# それぞれ、配列の最も右の数、最も左の数である。
max_pos_num = pos_nums[-1]
min_pos_num = pos_nums[0]
# min_pos_numが2以上ならば、1を返す。
if min_pos_num >= 2:
return 1
# 以下は、min_pos_numが1の場合。
# 仮に、pos_numsが、正の数が欠けていない配列ならば、
# それは初項 1，公差 1，項数 max_pos_numの等差数列である。等差数列の和の公式より、
# sum(pos_nums) == (1 + len(pos_nums)) * len(pos_nums) / 2
# が成り立つ。
# その場合には、len(pos_nums) + 1を返す。
if sum(pos_nums) == (1 + len(pos_nums)) * len(pos_nums) / 2:
return len(pos_nums) + 1
# 以下は、pos_numsが等差数列ではない場合。
# 仮に、pos_numsが、正の数がかけていない配列ならば、その位置と内容の間には
# pos_nums[i] == i + 1
# の関係が成り立つ。
# 内容 = 位置 + 1の関係が成り立たない最も左の場所を探し、
# その場所の直前の左の数に1を加えたものを、答えとして返す。
# この探索には、今回は線形探索を用いる。
#l: 二分探索の左側の端
#r: 二分探索の右側の端
#c: 二分探索の中央を示す。
l = 0
r = len(pos_nums) - 1
c = math.ceil((l + r) / 2)
while True:
# lとrが等しい時には、探索を終了する。
if l == r:
#l, r, cが示している場所は、等差数列を乱しているラインの右でもありうるし、左でもありうる。
#pos_nums[c] - pos_nums[c - 1] == 1 ならば、そのラインの左側である。
#l == 0 の場合も、そのラインの左側である。
if l == 0 or pos_nums[c] - pos_nums[c - 1] == 1:
return pos_nums[c] + 1
elif r == len(pos_nums) - 1 or pos_nums[c] - pos_nums[c - 1] != 1:
#pos_nums[c] - pos_nums[c - 1] == 1 ならば、そのラインの右側である。
return pos_nums[c - 1] + 1
return res
# pos_nums[c] == c + 1 が成り立つならば、lを現在のcより1つ右にずらす。
# そのうえでcを更新する。
if pos_nums[c] == c + 1:
l = min([r, c + 1])
c = math.floor((l + r) / 2)
continue
# pos_nums[c] == c + 1 が成り立たないならば、rを現在のcより1つ左にずらす。
# そのうえでcを更新する。
else:
r = max([l, c - 1])
c = math.floor((l + r) / 2)
continue
# 探索してもズレが見つからなかった場合には、-1を返す。
return -1
結果：
イイ感じですね！