自己紹介
初めまして。
本誌を訪問頂き有難うございます。
趣味で python を始めた中年おじさんです。
基礎から始めたくて記事を書き始めた今日この頃です。
本誌は基礎編 第二弾となっており、
以下の記事は、その前身である第一弾です。
学習目標
今回は Leetcode:Explorer Binary Search の理解を目標とします。
どのように理解するかは、以下のアプローチで進めます。
テンプレートの暗記 => 記述の理解(イメージ作成) => 自分なりのアプローチで再検証 => 理解の穴を埋める
試行錯誤を繰り返すことで理解が深まり、思考力が養われると思いますので
なるべく小さな発見を毎日 update できれば幸いです。
正直、二分探索の理解がまだまだなので時間をかけて磨いていきます。
概要
二分探索は昇順に整頓されたものから探索します。
この中から中央に配置された値が探索値と同等であれば 0 ~ 中央-1 に配置された
値が探索値と同等か確認する手間が省けます。
二分探索の計算量は log で表現されているのは知っていましたが
なぜなのかは理解できていませんでした。
あくまで私の理解ですが、要素数 N から値を探す場合、
(1/2) を n 回することで Goal に辿り着くのが二分探索です。
その理解で良ければ、N * (1/2)^n は 1 となるはずです。
前述の n は試行回数なので計算量といえます。
式を変形し、n について解いてみます。
n = log2(N)
以上から底を2とした探索範囲 N の対数を取ったものが計算量になることが分かりました。
エクセルでサクッとグラフにしてみました。
縦軸:n 計算量、横軸:N 探索範囲
40万個のデータからの探索は僅か 16 回で済むって凄いと思います。
ベーシックな探索で for 分を使い、端から確認していくリニア探索では、
要素数に比例するので、トンデモナイ計算量になります。
leetcode 先生の教えによると二分探索にはテンプレートがあり、
大半がこれらに当てはまるようです。先生の教えはこちらです。
理解できている物を以下に記載します。
テンプレート1
def BS(nums,target):
left,right = 0,len(nums)-1
while left <= right:
mid = (left + right)//2
if nums[mid] == target:
return mid
elif target < nums[mid]:
right = mid-1
else:
left = mid+1
return -1
leetcode 先生の御高説を筆者なりに噛み砕いた理解はコチラ↓↓です。
POINT 1更新時はleft, right = mid-1,mid+1 とし、前回の mid は次の検索では使用しない
昇順である配列で最初の if 文で mid != target と判断が出来たのであれば、
mid の要素を除いた領域である target < mid or mid < target の何れかに着目するために mid-1 or mid+1 とする。
POINT 2post-processing が不要
post-processing とは、探索後、left == right となるまで探索しきるのではなく、
left < right の状態で探索が終了するプログラムの場合、配列内に未探索の領域ができます。
post-processing はこの残りの要素についても探索処理を適用するプロセスを指しています。
Template#1 は left == right の条件も含めて探索するので、結果が fail であれば
探索値は含まれてなかったと判断することが出来ます。
テンプレート2
def BS(nums,target):
left,right = 0,len(nums)-1
while left < right:
mid = (left + right)//2
if nums[mid] == target:
return mid
elif target < nums[mid]:
right = mid-1
else:
left = mid+1
if(left != nums.size() && nums[left] == target) return left;
return -1
テンプレート2でも同様に探索をすることが出来ます。
テンプレート1 とは違いは何でしょうか？
現状の理解で伝えると処理時間に差があります。
例えば以下のような問題があったとします。
nums = [0,0,0,0,0,1,1,1] の中から 0,1 の境界線に隣接する最初の 1 の index を探してください。
つまり境界線を探す問題です。
試しに上記について検証してみました。
len(nums) = 2000 を用意し、0,1 の境界線となる 1 の位置を 1~ 2000 と振ってみたときの
処理時間を template 1, template 2 で比較してみました。
以下のグラフをご覧ください、赤線がテンプレート1, 青線がテンプレート2 です。
縦軸:処理時間、横軸:境界線の位置
勿論、nums 長と境界線の位置によって処理時間は変わるようですが、
template 2 の方が処理時間が速いことが分かります。
例題1 Binary Search
要素数 n かつ整数を整列させた nums と target をプレゼントしますので、nums から target を探す関数を記述してください。
発見した場合はインデックスを返し、存在しなければ -1 を返してください。
#Example 1:
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
#Example 2:
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
補足
nums の中には要素のダブりはナシです。
len(nums) は 1 ~ 1000
要素の値は -9999 ~ 9999 のいずれかです。
解説
二分探索とか置いておくと For 分で取り急ぎ解けます。
class Solution:
def search(self, nums: List[int], target: int) -> int:
for i in range(len(nums)):
if nums[i] == target:
return i
return -1
シンプルで個人的には好きなのですが、前述の概要にもあるように
計算量をなるべく減らしたいので二分探索していきたいと思います。
前述の Template#1 を使用してみます。
蛇足かもしれませんが要点をリマインドします。
POINT 1.
整列した配列から探索
POINT 2.
(Left + Right)//2 = Centerとし、nums[Center] が検索値との関係が =, < ,> のいずれかを確認
POINT 3.
POINT 2 で確認した関係を加味して以下のいずれかで Center 値を更新
・検索値 = nums[Center] なら goal,
・検索値 < nums[Center] なら (Left + Right(=Center-1))//2 = Center ,
・検索値 > nums[Center] なら (Left(=Center+1) + Right)//2 = Center
Center 値を更新したら、再度 POINT2 にある nums[Center] と 検索値の関係確認のフローへ
POINT 4.
POINT 2 <=> POINT 3 を反復し、Left == Right となっても見つからなければ、答えはないと判断
以上の POINT を意識しつつ問題を振り返ると
検索値にヒットしたインデックスを return し
検索値がヒットしない場合は、-1 を return
とあります。
これを意識して書くと以下のようになります。
class Solution:
def search(self, nums: List[int], target: int) -> int:
left,right = 0,len(nums)-1
while left <= right:
center = (left + right)//2
if nums[center] == target:
return center #検索値 hit !! return index
elif nums[center] > target:
right = center - 1
else:
left = center + 1
return -1 #検索値 not hit !! return -1
mid,center の表記が違うだけで、実は Template #1 そのままです(笑)
演習 1 Sqrt
正の整数 x の累乗根を求めてください。
但し、出力する値は整数が欲しいので、小数点以下は切り捨ててください。
#Example 1:
Input: x = 4
Output: 2
#Example 2:
Input: x = 8
Output: 2
#補足: 8 の累乗根は2.82842...。
# 小数点以下を切り捨てると答えは 2 になります。
[制約]
0 <= x <= 2**31 - 1
解説
二分探索と累乗根に何の関係があるのか全く見当も付きませんでしたが、
整数 x と、その累乗根には以下の関係があるそうです。
x ＜ 2 の場合:output == x
x ≧ 2 の場合:出力すべき累乗根の値は必ず 0 < SqrtNums < x/2
x が 2 未満ではない場合、2 < SqrtNums < x/2 から近い値を探します。
この時に二分探索を用います。
x が 9, 16, 25, 36 の場合、
探索で 3, 4, 5, 6 と求める事が出来そうです。
しかし、残念なことに 0 <= x <= 2**31 - 1 とあるので
小数点以下を切り捨てて回答する必要があります。
まずは以下の記述をご覧ください。
class Solution:
def mySqrt(self, x: int) -> int:
if x < 2:return x
left,right = 2,x//2
while left <= right:
center = (left+right)//2
nums = center*center
if nums > x: right = center-1
elif nums < x: left = center+1
else:return center
return right
最後にしれっと return right とありますが、
この記述が求められている切り捨ての output をするための重要な記述になります。
また二分探索を進めていくと left = right = center となります。
例を挙げてみます。
| / | x = 35 の場合 | x = 36 の場合 | x = 37 の場合 |
|---|---|---|---|
| 1回目 | C**2=25(L,C,R = 2,5,9) | C**2=25(L,C,R = 2,5,9) | C**2=25(L,C,R = 2,5,9) |
| 2回目 | C**2=49(L,C,R = 6,7,9) | C**2=49(L,C,R = 6,7,9) | C**2=49(L,C,R = 6,7,9) |
| 3回目 | C**2=36(L,C,R = 6,6,6) | C**2=36(L,C,R = 6,6,6) | C**2=36(L,C,R = 6,6,6) |
| 4回目 | C**2=36(L,C,R = 6,5,5) | None | C**2=36(L,C,R = 7,6,6) |
| 答え | Ans = 5(=R) | Ans = 6(=L/R/C) | Ans = 6(=R) |
※L : Left , C : Center, R: Right
面白いことに4 回目に着目すると x = 35 の場合、R = C-1 を適用し
x = 37 の場合、L = C + 1 を適用していますが答えは R が正解になっています。
以上のような背景があって return right という記述になっています。
規則性を見つけるためには簡単な x = 36 のケースから±1 で検証すると
比較的早くたどり着けます。
演習 2 Guess Number Higher or Lower
推理ゲームをしています。そのルールは以下になります。
1.A さん：1 ~ n のいずれかから数字をピックします。
2.あなた: A さんがピックした数字を推理してください。
推測の補助として API : guess() を用意されています。
API にあたなの推理値を入力すると以下の出力を得られます。
・A さんがピックした値 > あなたの推理した値: -1
・A さんがピックした値 < あなたの推理した値: 1
・A さんがピックした値 = あなたの推理した値: 0
API の出力をヒントにピックした数字を言い当ててください。
#Example 1:
Input: n = 10, pick = 6
Output: 6
#Example 2:
Input: n = 1, pick = 1
Output: 1
#Example 3:
Input: n = 2, pick = 1
Output: 1
#Example 4:
Input: n = 2, pick = 2
Output: 2
[制約]
1 <= n <= 231 - 1
1 <= pick <= n
解説
今回は API を使って数字を言い当てる問題です。
また API を使う回数に関しても制限が記載されていないので、
何回 API を使ってもよい理解になります。
A さんに high or low の質問を繰り返せば、
二分探索で必ずA さんがピックした値 = あなたの推理した値となります。
よって、while 分を抜けた後の return の記述はなくても問題ない理解をしました。
# The guess API is already defined for you.
# @param num, your guess
# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
# def guess(num: int) -> int:
class Solution:
def guessNumber(self, n: int) -> int:
low,high = 1,n
while low <= high:
mid = (low+high)//2
res = guess(mid)
if res == 0:return mid
elif res < 0 :high = mid-1
else : low = mid+1
演習 3 Search in Rotated Sorted Array
昇順で整頓した nums と、整数 target をプレゼントします。
ただし、予め、あなたには秘密で nums 内の中身がピボットされていると仮定します。
nums 内をピボットされていたとしても、target のインデックスをキッチリ output してほしいです。
宜しくお願い致します。
#Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
#Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
#Example 3:
Input: nums = [1], target = 0
Output: -1
[制限]
1 <= nums.length <= 5000
-104 <= nums[i] <= 104
要素にダブりはナシです.
nums はあるピボットで必ず中身が回転しています。
-10**4 <= target <= 10**4
解説
nums を右 or 左のどちらかの方向に何回か回転させた物から target を探していきます。
どうやって探していくか悩ましいですが、
二分探索は昇順で整頓された配列から探索していくことを思い出して考えていきます。
if 分で場合分けし、昇順である要素を見つけ、その中で探索していきます。
POINT1.start <==> center or center <==> end のいずれかに昇順は必ず存在している
POINT2.POINT1 で定義した昇順の領域を二分探索
前述の POINT1 ですが、本当にそうなのでしょうか。
以下は一例ですが、配列を回転させたものを表にしています。
| 回転数 | nums |
|---|---|
| 0 | [0,1,2,4,5,6,7] |
| 1 | [7,0,1,2,4,5,6] |
| 2 | [6,7,0,1,2,4,5] |
| 3 | [5,6,7,0,1,2,4] |
| 4 | [4,5,6,7,0,1,2] |
| 5 | [2,4,5,6,7,0,1] |
| 6 | [1,2,4,5,6,7,0] |
| 7 | [0,1,2,4,5,6,7] |
全てのパターンを例示できなくて申し訳ないです。
前述の表は要素を左側方向にシフトした場合を表しています。
大元のデータが昇順であるものを使用している限り、left,right, mid (=left+right//2) を駆使できれば
二分探索できる領域はいずれの場合でも何処かに必ずあることが分かります。
前述は左方向ですが、右方向に移動させたとしても基本は同じです。
class Solution:
def search(self, nums: List[int], target: int) -> int:
start,end = 0,len(nums)-1
while start <= end:
center = (start + end)//2
if nums[center] == target:
return center
elif nums[start] <= nums[center]:
if nums[start] <= target and target < nums[center]:
end = center-1
else:
start = center + 1
else:
if nums[center] < target and target <= nums[end]:
start = center + 1
else:
end = center -1
return -1
前述にあるように、一回目の num[mid] の値から
最初のふるいにかけるのは問題ないと思います。
次は、left , right をどのように更新していくかです。
また、追い込んで絞った領域内が昇順になっていない場合が難しいところです。
以下のケースで考えていきます。
nums = [6,7,1,2,3,4,5]
target = 1
前述のプログラムだと一回目の探索により範囲は [6,7,1] に絞られます。
見ていただくと分かるとおり、6,7 だけが昇順ですが 1 は完全に部外者です。
どうしましょう。。
以下は回答のプログラムから一部抜粋していますが、微力ながらコメントをつけてみました。
1 がどのように扱われているのか確認できます。
#search area is [6,7,1]
#first, we have to define the mid from left and right value
#As you know,center = (start + end)//2. so the result is bellow.
#start =nums[0]
#end =nums[2]
#center=nums[1]
# nums[start] <= nums[center] is True.
elif nums[start] <= nums[center]:
# Does it satisfy the bellow condition? No. because target == nums[center]
if nums[start] <= target and target < nums[center]:
end = center-1
# The bellow condition is True.
else:
start = center + 1
#after the throughing that action.start,end,center are changed as bellow.
#start =nums[2]
#end =nums[2]
#center=nums[2]
#center=nums[2] means 1.
#So the next execution in while roop will treat it as "if nums[center] == target"
#you can get "return center"
この問題で再確認したのは、要素全体が昇順でなくても、left / right 間が昇順でなくても
left <==> center or center <==> right で昇順であれば探索が出来るということです。
そのため前述にあるように [6,7,1] であっても切り分ける事ができるのでした。
勉強になりました。
例題2 First Bad Version
貴方はプロダクトマネージャーで、現在、新製品開発チームを指揮しています。
残念ながら最終版のプロダクトが品質チェックで落ちてしまいました。
既存設計のバージョンアップを繰り返すことで最終版としていました。
既存設計には n 個のバージョンがあり、バグを孕んだ最初のバージョンを探したいと思います。
貴方には API: isBadVersion が与えられており、バージョンを入力することでバグの有無を確認してくれます。
この API を使って、バグを孕んだ最初のバージョンを見つける機能を実装してください。また API の call は最小限にしてください。
#Example 1:
Input: n = 5, bad = 4
Output: 4
#Explanation:
#call isBadVersion(3) -> false
#call isBadVersion(5) -> true
#call isBadVersion(4) -> true
#isBadVersion が false なのであればバグなし、True ならバグあり
#バグを発見した最初のバージョンは 4 です。
#Example 2:
Input: n = 1, bad = 1
Output: 1
制約:
1 <= bad <= n <= 2**31 - 1
解説
今回はバージョンを求める問題なので、
一番古いバージョンを low と定義し、一番新しいバージョンを high とします。
もちろん、間のバージョンは mid とします。
一回目の探索で API の出力が False の場合、mid も含め、
それ以下の古いバージョンは全て False になります。
よって、次の探索は low = mid + 1 とします。
しかし、一回目の探索で API の出力が True の場合、以下の 2 つが選択肢として考えられます。
1.バグを孕んだ最初のバージョン、つまり回答である可能性
2.もっと古いバージョンが回答である可能性
現在地が回答である可能性がある以上は high = mid -1 とせずに、
high = mid として探索した方がよさそうです。
class Solution:
def firstBadVersion(self, n):
low,high = 1,n
while low < high:
mid = (low + high)//2
if isBadVersion(mid):
high = mid #mid が回答である可能性が有る
else:
low = mid+1#mid が回答である可能性は無い
return low
演習2 Find Peak Element
頂上値は隣接する値よりも大きい要素とします。
整数の集合体 nums から頂上値を見つけ、その index を返してください。
もし複数の頂上値を見つけた場合、いずれかの index を返します。
#Example 1:
Input: nums = [1,2,3,1]
Output: 2
#Explanation: 3 is a peak element and your function should return the index number 2.
#Example 2:
Input: nums = [1,2,1,3,5,6,4]
Output: 5
#Explanation: Your function can return either index number 1 where the peak element is 2,
#or index number 5 where the peak element is 6.
制約:
1 <= nums.length <= 1000
-231 <= nums[i] <= 231 - 1
nums[i] != nums[i + 1] for all valid i.
解説
以下の条件を満たした center (中央値)を返せれば Goal になります。
POINT1.右に比べて中央値の方が大きい
POINT2.左に比べて中央値の方が大きい
二分探索は探索が進むにつれて left == right になるタイミングが出来ます。
POINT3.前述の POINT 1、2 を満たした後に left == right となれば、return left or right
上記を再帰処理することが出来ればとアプローチしたのが以下になります。
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
def search(nums,left,right):
if left == right:
return left
center = (left+right)//2
if nums[center] > nums[center+1]:
return search(nums,left,center)
return search(nums,center+1,right)
return search(nums,0,len(nums)-1)
念のため動きを追ってみます。
演習 3 Find Minimum in Rotated Sorted Array
配列長 n の配列は昇順で整列しているのですが、1 ~ n 回、回転させたとします。
例えばですが、nums = [0,1,2,4,5,6,7] を回転させてみます。
4回転 : [4,5,6,7,0,1,2]
7回転 : [0,1,2,4,5,6,7]
回転について補足すると
[a[0], a[1], a[2], ..., a[n-1]] を1回転させると
[a[n-1], a[0], a[1], a[2], ..., a[n-2]]となります。
以上から与えられた配列から最小値を見つけてください
#Example 1:
Input: nums = [3,4,5,1,2]
Output: 1
#Explanation: The original array was [1,2,3,4,5] rotated 3 times.
#Example 2:
Input: nums = [4,5,6,7,0,1,2]
Output: 0
#Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.
#Example 3:
Input: nums = [11,13,15,17]
Output: 11
#Explanation: The original array was [11,13,15,17] and it was rotated 4 times.
制約:
n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
All the integers of nums are unique.
nums is sorted and rotated between 1 and n times.
解説
問題で定義されている"回転"について整理します。
問題文は以下のように記載があります。
[a[0], a[1], a[2], ..., a[n-1]] を1回転させると
[a[n-1], a[0], a[1], a[2], ..., a[n-2]]となります。
上記の説明だと、例えば [0,1,2,4,5,6,7] を3回転させた場合、
以下の過程を経ることになります。
| 回転数 | nums |
|---|---|
| 0 | [0,1,2,4,5,6,7] |
| 1 | [7,0,1,2,4,5,6] |
| 2 | [6,7,0,1,2,4,5] |
| 3 | [5,6,7,0,1,2,4] |
| 4 | [4,5,6,7,0,1,2] |
| 5 | [2,4,5,6,7,0,1] |
| 6 | [1,2,4,5,6,7,0] |
| 7 | [0,1,2,4,5,6,7] |
一応、問題文で定義された 4,7 回転の結果と
一致しますので理解に問題はなさそうです。
では、最小値を炙り出すための条件を整理していきます。
まずは、最初から最小値が num[0] に位置している場合です。
POINT1.nums[0] < nums[right] の場合、nums[0] が最小
| 回転数 | nums |
|---|---|
| 0 | [0,1,2,4,5,6,7] |
次は最初の mid (=left + right)//2 で見事、最小値を射抜く場合
以下の POINT 2,3 が該当します。
POINT2.nums[mid] > nums[mid+1] の場合、nums[mid+1] が最小
POINT3.nums[mid-1] > nums[mid] の場合、nums[mid] が最小
POINT2,3 がなぜ、最小値に該当するのでしょうか。
問題を思い出してみてください。
基本は昇順である配列を扱う場合、nums[left] < nums[right] が必ず成立します。
しかし、今回の問題にあるように幾重にも回転させた場合、nums[left] > nums[right] となる条件はなんでしょうか？
その答えは以下の表です。
| 回転数 | nums |
|---|---|
| 3 | [5,6,7,0,1,2,4] |
| 4 | [4,5,6,7,0,1,2] |
以上のように、nums[left] > nums[right] となる条件が何処にあるかを
探すことが最小値を探す手掛かりになります。
前述にあるように、探索前に最小を見つけたり、
一回の探索で最小を見つける手法は理解しました。
しかし、それでも見つからない場合、どうやって探していけばいいでしょうか。
以下の表を眺めてみます。
| 回転数 | nums |
|---|---|
| 1 | [7,0,1,2,4,5,6] |
| 2 | [6,7,0,1,2,4,5] |
| 5 | [2,4,5,6,7,0,1] |
| 6 | [1,2,4,5,6,7,0] |
以下の POINT 4 が見えてきた気がします。
POINT4.
1,2回目に着目すると nums[0] > nums[mid] の場合、right = mid - 1
5,6回目に着目すると nums[0] < nums[mid] の場合、left = mid + 1
POINT4 で移動した後、POINT2,3 で最小値を探索することが出来る事が分かります。
以上をまとめると以下のコードになります。
class Solution(object):
def findMin(self, nums):
if len(nums) == 1:
return nums[0]
left,right = 0,len(nums)-1
if nums[0]< nums[right]: #POINT1
return nums[0]
while left <= right:
mid = (left+right)//2
if nums[mid] > nums[mid+1]:#POINT2
return nums[mid+1]
if nums[mid-1] > nums[mid]:#POINT3
return nums[mid]
if nums[0] < nums[mid]:#POINT4
left = mid+1
else:
right = mid-1
演習4 Search for a Range
昇順でソートされた整数の集合 nums から target と同一となる並びの最初と最後の index を探してください。
もし、ターゲットが無い場合は [-1,-1] で構いません。
#Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
#Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
#Example 3:
Input: nums = [], target = 0
Output: [-1,-1]
制約:
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums is a non-decreasing array.
-109 <= target <= 109
解説
左から順番にリニア探索でチェックします。
もし何も見つからなかったら [-1,-1]で終了します。
見つかったら left とし、右から同じように探索します。
問題には細かく記載がないですが、
start と end のインデックスが同じ場合もあります。
また start と end 間が 3 つ以上の場合も想定しなければなりません。
以下の記述が個人的にはリーズナブルだと思います。
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
left,right = 0,0
if len(nums) == 0: return[-1,-1]
for i in range(len(nums)):
if nums[i] == target:
left = i
break
elif i == len(nums)-1:
return [-1,-1]
for j in range(len(nums)-1,0,-1):
if nums[j] == target:
right = j
break
return [left,right]
しかし、本誌の題名にあるように二分探索とありますので、
何とか二分探索のアプローチも身に着けたいと思います。
leetcode 先生の教えによると以下が回答になります。
class Solution:
def extreme_insertion_index(self, nums, target, left):
lo = 0
hi = len(nums)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] > target or (left and target == nums[mid]):
hi = mid
else:
lo = mid+1
return lo
def searchRange(self, nums, target):
left_idx = self.extreme_insertion_index(nums, target, True)
if left_idx == len(nums) or nums[left_idx] != target:
return [-1, -1]
return [left_idx, self.extreme_insertion_index(nums, target, False)-1]
nums = [1,2,3,4,5,6]
target = 4
S=Solution()
print(S.searchRange(nums,target))
コードの構成が筆者には高度過ぎて悩ましいところですが、
[-1,-1] となる条件としては、left_idx == len(nums)、つまり
左から探しだして右端 + 1 になったので何も該当値が無かったことになります。
target の値が与えられた配列の要素と比べて大きいものであれば右端に行くことは出来るのですが、
target が小さい場合、左側に寄っていくことになります。
どこで止まるかも分からないので、最終的には target と同等でない場合は Fail と考えるのが
妥当なのだと思います。
取り急ぎ動きを追ってみました。
演習5 Find K Closest Elements
整頓された arr,整数 k と x があります。
x に近い整数を k 個 arr の中から取り出してください。
output は昇順である必要があります。
整数 a よりも b の方が x に近い事を確認する条件は以下です。
|a - x| < |b - x|, or
|a - x| == |b - x| and a < b
#Example 1:
Input: arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]
#Example 2:
Input: arr = [1,2,3,4,5], k = 4, x = -1
Output: [1,2,3,4]
制約:
1 <= k <= arr.length
1 <= arr.length <= 10^4
arr is sorted in ascending order.
-10^4 <= arr[i], x <= 10^4
解説
class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
left, right = 0, len(arr) - k
while left < right:
mid = (left + right) // 2
# x より左側の要素 VS. x より右側の要素
if x - arr[mid] > arr[mid + k] - x:
left = mid + 1
else:
right = mid
return arr[left:left + k]
演習6 Closest Binary Search Tree Value
二分探索木をプレゼントしますので、target に近い値を探してください。
補足:
target は floating point です
また探索木のなかで target に最も近い値は 1 つだけであることが保障されています。
Input: root = [4,2,5,1,3], target = 3.714286
4
/ \
2 5
/ \
1 3
Output: 4
解説
まずは回答です。
class Solution:
def closestValue(self, root: TreeNode, target: float) -> int:
Min = root.val
while root:
Min = min(Min,root.val,key = lambda x:abs(target-x))
root = root.left if target < root.val else root.right
return Min
上記を理解するためにも
lambda を理解する必要がありました。
いわば即席関数っといったところでしょうか。
まずは、以下のサンプルをご覧ください。
test = lambda a,b:a+b
print(test(1,2))
#output: 3
lambda を使って a + b の関数を test としています。
しかし、回答にある key は(1,2) とはしていません。
そこで、step2.py のサンプルです。
target = 2
closest = min(2,1,key = lambda x:abs(target-x))
print(closest)
#output: 2
closest の中に用意している min は x=2 or 1 の場合で、
abs(target-x)の結果、小さい方の結果になる要素は2,1 のどちらでしょうか？っと聞いています。
勿論、2 です。
以上から前述のコードで何をしたいか見えてくると思います。
また今回の探索のフィールドが二分探索であることも味噌です。
target < root.val であれば root.val よりも小さい要素は左に集まっていますから
次の探索では root = root.left としています。
演習7 Search in a Sorted Array of Unknown Size
昇順に並べた配列をプレゼントするので、target を探す機能を実装してください。
target を見つけたら index を返してくれれば OK です。無ければ -1 を下さい。
しかし、配列のサイズは不明とします。
与えられた手段として ArrayReader.get(k) として index を入力することで
要素を得る事が出来ます。
推察されているように配列は 10000 個以下であり、これを超えると
ArrayReader.get は 2147483647 を返します。
#Example 1:
Input: array = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
#Example 2:
Input: array = [-1,0,3,5,9,12], target = 2
Output: -1
#Explanation: 2 does not exist in nums so return -1
制約:
要素内にダブりはナシ
配列内は -9999 ~ 9999 のいずれかを採用
配列長は 1 ~ 10^4
解説
問題文には要素は 10^4 以下とあるので、
ココを maximum とみても良さそうです。
概要にあるように二分探索は 40万個でも 16~7 回で探索できるので問題ないです。
class Solution:
def search(self, reader, target):
left,right = 0,10**4
while left <= right:
mid = (left+right)//2
if reader.get(mid) == 2147483647:
right = mid-1
elif reader.get(mid) == target:
return mid
elif reader.get(mid) < target:
left = mid+1
else:
right = mid-1
return -1
演習8 Pow(x, n)
Implement pow(x, n), which calculates x raised to the power n (i.e. xn).
pow(x,n) を実装してください。
x を n乗するイメージです。
#Example 1:
Input: x = 2.00000, n = 10
Output: 1024.00000
#Example 2:
Input: x = 2.10000, n = 3
Output: 9.26100
#Example 3:
Input: x = 2.00000, n = -2
Output: 0.25000
#Explanation: 2-2 = 1/22 = 1/4 = 0.25
制約:
-100.0 < x < 100.0
-231 <= n <= 231-1
-10^4 <= xn <= 10^4
解説
二分探索でも再帰処理でもないですが
思いついたのは以下の記述です。
#runtime 36ms
#memory usage 14.2MB
class Solution:
def myPow(self, x: float, n: int) -> float:
return x**n
#runtime 20ms
#memory usage 14.3MB
class Solution:
def myPow(self, x: float, n: int) -> float:
def helper(x,n):return x**n
if n == 0:
return 1
half = helper(x,n//2)
if n % 2 == 0:
return half * half
else:
return half * half * x
ご覧のとおり二分探索でもないので
今後の課題としようかと思います。
シンプルに x^n が答えになるのですが、
後者のプログラムは場合分けをしています。
また計算を早めるためにx^(n/2 * 2) という考え方を使って、
x^(n/2)を計算した後に、それを2 回掛けることで output を求めています。
勿論、leetcode 先生の教えです(笑)
演習9 Valid Perfect Square
正の整数 num をプレゼントするので、正方形と判断出来たら return
出来なかったら false を返してください。
#Example 1:
Input: num = 16
Output: true
#Example 2:
Input: num = 14
Output: false
制約:
1 <= num <= 2^31 - 1
解説
演習 1 の派生問題だと思います。
class Solution:
def isPerfectSquare(self, num: int) -> bool:
if num <2:return True
left,right = 0,num//2
while left <= right:
mid = (left+right)//2
if mid*mid == num:
return True
elif mid*mid < num:
left = mid + 1
else:
right = mid -1
return False
演習10 Find Smallest Letter Greater Than Target
整頓した文字列と target の文字をプレゼントします。
target よりも大きい文字列の中で最も小さい文字を見つけてください。
例えば ['a', 'b'] , target = 'z' とすると、回答は a です。
文字の順番は回転して考える必要があります。
#Examples:
Input:
letters = ["c", "f", "j"]
target = "a"
Output: "c"
Input:
letters = ["c", "f", "j"]
target = "c"
Output: "f"
Input:
letters = ["c", "f", "j"]
target = "d"
Output: "f"
Input:
letters = ["c", "f", "j"]
target = "g"
Output: "j"
Input:
letters = ["c", "f", "j"]
target = "j"
Output: "c"
Input:
letters = ["c", "f", "j"]
target = "k"
Output: "c"
制約:
文字列は 1 <= length <= 10000
文字列はダブりなしで、基本小文字です
解説
二分探索をしたいのですが以下の要素を
最初に取り除かないとうまく動きません。
target < letter[0]
or
letter[-1] < target
or
letter[-1] == target の何れかの場合 return letter[0]
class Solution:
def nextGreatestLetter(self, letters: List[str], target: str) -> str:
if letters[-1] <= target or letters[0] > target:
return letters[0]
left,right = 0,len(letters)-1
while left <= right:
mid = (left+right)//2
if letters[mid] <= target: #Point1
left = mid+1
else:
right = mid-1
return letters[right+1]
POINT1
left == right になった場合、Point1 に遷移するので
right が target に一番近い point に right が居ることになります。
一番近いとは target 以下の index です。
よって、最後は right+1 の letters を返せば goal になります。
演習11 Find Minimum in Rotated Sorted Array II
昇順に整理された配列を貴方に届ける前に数回、回転させました。
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
最小値を探してください。
因みに要素にダブりがある可能性もあります。
#Example 1:
Input: [1,3,5]
Output: 1
#Example 2:
Input: [2,2,2,0,1]
Output: 0
解説
今回のポイントはダブったら high -= 1 とする事です。
それ以外はいつも通りで大丈夫です。
class Solution:
def findMin(self, nums: List[int]) -> int:
low = 0
high = len(nums)-1
while high > low:
pivot = low + (high - low) // 2
if nums[pivot] < nums[high]:
high = pivot
elif nums[pivot] > nums[high]:
low = pivot + 1
else:
high -= 1
return nums[low]
GIF で追いかけてみました。
演習12 Intersection of Two Arrays
2つの配列をプレゼントするので、共通する要素を引き抜いてください。
#Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]
#Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
メモ:
要素にダブりはナシです。
output は好きな順序で大丈夫です。
解説
二分探索として学習すべきかもしれませんが、
以下の記述が至ってシンプルで良いと思います。
class Solution:
def intersection(self, nums1, nums2):
set1 = set(nums1)
set2 = set(nums2)
return list(set1 & set2)
演習13 Intersection of Two Arrays II
2つの配列をプレゼントするので、共通する要素を引き抜いてください。
#Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]
#Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]
解説
collection 初投入です。
counter を使うことで nums1, nums2 でそれぞれ
何を何個あるのか確認します。
更に & して残ったものを c に代入します。
最後に for 分 + items を組み合わせて
何を何個という情報から何 x 何個 をそのまま出力することで答えとしています。
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
c = Counter(nums1) & Counter(nums2)
ans = []
for k, v in c.items():
ans.extend([k] * v)
return ans
演習14 Two Sum II - Input array is sorted
昇順に整頓された配列をプレゼントしますので、
その中から 2 つを選んで target となる組み合わせを見つけてください。
index を 2 つ返してください。
要素にダブりはナシです。
#Example 1:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
#Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.
#Example 2:
Input: numbers = [2,3,4], target = 6
Output: [1,3]
#Example 3:
Input: numbers = [-1,0], target = -1
Output: [1,2]
解説
二分探索であるかは分かりませんが、
以下のようなアプローチはいかがでしょうか。
左右、両端から一個ずつ潰していくやり方です。
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left,right = 0, len(numbers)-1
while left < right:
nums = numbers[left] + numbers[right]
if nums == target:
return (left+1,right+1)
elif nums < target:
left += 1
else:
right -= 1
return [-1,-1]
演習15 Find the Duplicate Number
n + 1 個の要素で構成された nums を差し上げます。
よって、要素数は 1 以上 n 以下になります。
その要素には 1 つだけダブりがありますので、
それを見つけてください。
#Example 1:
Input: nums = [1,3,4,2,2]
Output: 2
#Example 2:
Input: nums = [3,1,3,4,2]
Output: 3
#Example 3:
Input: nums = [1,1]
Output: 1
#Example 4:
Input: nums = [1,1,2]
Output: 1
解説
二分探索での output が出来なかったので
次回再チャレンジします。
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
#104ms
Dlist = Counter(nums)
for i,j in Dlist.items():
if j >= 2:
return i
"""
#2432ms
while nums:
sample = nums.pop(0)
if sample in nums:
return sample
"""
演習15 Median of Two Sorted Arrays
要素数をそれぞれ m , n としたソート済みの配列 nums1,nums2 を差し上げます。
nums1,nums2 を合わせた配列から真ん中の値を返してください。
#Example 1:
Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
#Explanation: merged array = [1,2,3] and median is 2.
#Example 2:
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
#Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
#Example 3:
Input: nums1 = [0,0], nums2 = [0,0]
Output: 0.00000
#Example 4:
Input: nums1 = [], nums2 = [1]
Output: 1.00000
#Example 5:
Input: nums1 = [2], nums2 = []
Output: 2.00000
解説
二分探索ではありませんが、
二分探索の特性を使って解いています。
今回は len(nums) が奇数であれば mid = (left + right)//2 が必ず中央に来ます。
よって return nums[mid] で良いです。
しかし、len(nums) が偶数の場合、例えば len(nums) = 4 の場合は mid は 1となります。
(nums[1] + nums[2])/2 で答えが出ます。
これをすべての偶数だった場合に当てはめて考えたのが以下の解です。
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
nums = sorted(nums1+nums2)
l,r = 0, len(nums)-1
m = (l+r)//2
if len(nums)%2 == 1:
return nums[m]
else:
return (nums[m] + nums[m+1])/2
演習16 Find K-th Smallest Pair Distance
与えられた配列の中に複数ある要素 k 間の距離で最小である物を求めてください。
#Example 1:
Input:
nums = [1,3,1]
k = 1
Output: 0
#Explanation:
#Here are all the pairs:
#(1,3) -> 2
#(1,1) -> 0
#(3,1) -> 2
#Then the 1st smallest distance pair is (1,1), and its distance is 0.
解説
class Solution():
def smallestDistancePair(self, nums, k):
def possible(guess):
count = left = 0
for right, x in enumerate(nums):
while x - nums[left] > guess:
left += 1
count += right - left
return count >= k
nums.sort()
lo = 0
hi = nums[-1] - nums[0]
while lo < hi:
mi = (lo + hi) // 2
if possible(mi):
hi = mi
else:
lo = mi + 1
return lo
演習17 Split Array Largest Sum
配列をプレゼントするので index m で分割した両者の合算から大きい方を返してください。
#Example 1:
Input: nums = [7,2,5,10,8], m = 2
Output: 18
#Explanation:
#There are four ways to split nums into two subarrays.
#The best way is to split it into [7,2,5] and [10,8],
#where the largest sum among the two subarrays is only 18.
#Example 2:
Input: nums = [1,2,3,4,5], m = 2
Output: 9
#Example 3:
Input: nums = [1,4,4], m = 3
Output: 4
解説
class Solution:
def splitArray(self, nums: List[int], m: int) -> int:
max_e = max(nums)
total_sum = sum(nums)
l, r = max_e, total_sum
ans = None
while (l <= r):
mid = (l + r) // 2
sum_so_far = 0; partitions_so_far = 1
for e in nums:
if sum_so_far + e > mid:
# Need to split
sum_so_far = e
partitions_so_far += 1
else:
# keep going
sum_so_far += e
if partitions_so_far <= m:
r = mid - 1
ans = mid
else:
l = mid + 1
return ans
演習18 Pow(x, n)
Implement pow(x, n), which calculates x raised to the power n (i.e. xn).
#Example 1:
Input: x = 2.00000, n = 10
Output: 1024.00000
#Example 2:
Input: x = 2.10000, n = 3
Output: 9.26100
#Example 3:
Input: x = 2.00000, n = -2
Output: 0.25000
#Explanation: 2-2 = 1/22 = 1/4 = 0.25
解説
class Solution:
def myPow(self, x: float, n: int) -> float:
if n < 0:
x = 1/x
n = -n
ans = 1
while n > 0:
if n % 2 == 1:
ans *= x
x *= x
n = n//2
return ans
素晴らしい!!勉強になりました。