解いた問題
LeetCode 88. Merge Sorted Array
昇順に並んだ2つのリストがあり、それぞれの要素数を表す数値も与えられる。
1つのリストに昇順でまとめてねって問題。
最初の解法
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
for i in range(n):
left = 0
right = m - 1
mid = (left + right) // 2
while left <= right:
if nums2[i] == nums1[mid]:
nums1.insert(mid, nums2[i])
break
elif nums2[i] > nums1[mid]:
left = mid + 1
if nums1[left] >= nums2[i]:
nums1.insert(left, nums1[i])
break
else:
right = mid - 1
if nums1[right] <= nums2[i]:
nums1.insert(right, nums1[i])
break
m += 1
以前学んだ二分探索が効くのではと思い試したら下記のようにエラーが出た。
Time exceedなんてあるのか（驚愕
どっか無限ループありそうだなと思ったらmidをfor内でいじってなかった。
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
for i in range(n):
left = 0
right = m - 1
while left <= right:
mid = (left + right) // 2
if nums2[i] == nums1[mid]:
nums1.insert(mid, nums2[i])
break
elif nums2[i] > nums1[mid]:
left = mid + 1
if nums1[left] >= nums2[i]:
nums1.insert(left, nums1[i])
break
else:
right = mid - 1
if nums1[right] <= nums2[i]:
nums1.insert(right, nums1[i])
break
m += 1
修正したけど失敗。
nums1にない数値がうまく入ってなさそう。
rightが0以下, leftの右が0の時に数値無理やり入れたら解決するかなと思い下記のように変更。
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
for i in range(n):
left = 0
right = m - 1
while left <= right:
mid = (left + right) // 2
if nums2[i] == nums1[mid]:
nums1.insert(mid, nums2[i])
break
elif nums2[i] > nums1[mid]:
left = mid + 1
if nums1[left] >= nums2[i] or nums1[left] == 0:
nums1.insert(left, nums1[i]) # ここ
break
else:
right = mid - 1
if nums1[right] <= nums2[i] or right < 0:
nums1.insert(right, nums1[i]) #ここ
break
m += 1
なんだこれ。
ここでギブアップ。AIに聞いたところ、nums2を入れるところをnums1の値を入れているのがまずおかしい`とのこと。
上記のコメント部分がそう。直したら下記のようになる。
インサート自体はうまくできてそうだが0が残るのと、入力が0の空リストの時挙動がおかしくなるっぽい
正解
2ポインタ法の応用を使うらしい。
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
i = m - 1 # nums1の読み込みポインタ
j = n - 1 # nums2の読み込みポインタ
k = m + n - 1 # 書き込みポインタ
while j >= 0:
if i >= 0 and nums1[i] > nums2[j]: # jをできる限り早く消したいから=なし。i>=0を入れないとi[-1]との比較が走りnum2の値が小さいときうまくnums1に反映されない
nums1[k] = nums1[i] # 値を移すのではなくコピーで十分。
i -= 1 # デクリメントして読み込みポインタを前にずらしていく
else:
nums1[k] = nums2[j]
j -= 1
k -= 1
後ろから行くのかぁ。
「コピーで十分」「後ろから走査する」「走査し終わったら止める」「片方走査しきったらその場で終了」あたりがアルゴリズム特有な考えだなと。
計算量は$O(m+n)$。定数倍と言えなくもないからnオーダーかなと思ったが明確に2つの入力サイズに依存するときは明記する必要がありそう。
ビッグオー記法自体、入力サイズを変数で表す記法だから当たり前っちゃ当たり前か。
感想
AIない時代は答え出るまで一人で考えなきゃいけなかったのか？いやコメント見て答えわかるか。
それだと最初の一人はどうやって答えを出しているんだ...？
あとこれがEasyなことに絶望を感じる。いつになったらMediumを解けるようになるのやら。
逆に言えばMediumを解けるようになった時の快感がやばそうだなと思ったら今のしんどさも面白くなってきた。
問題に関して、昇順って特性ガン無視しちゃったなあと反省。
どうしてもいつも数字を読む方向から何かを作用させようと無意識的に考えてしまう。
アルゴリズムを解く際には頭を柔らかく、というかいつも読んでいる方向が何かを自覚し、それ以外の読み方がないかを探すことが大事かもしれないと考えた。