問題
小さいnums と、target をnums のtarget がtarget を
numsの値は 小さい 順に 並び、 同じ値は 2 回出てきません numsの長さは 0 以上 10000 以下、 値は どれも -10000 以上 10000 以下です。 空の ときの 答えは 0 です - 時間は O(log n) で
解いてください
入力と出力の例
例 1
target が
入力
nums = [-3, 2, 7, 11]
target = 7出力
2例 2
8 は 7 と 11 の
入力
nums = [-3, 2, 7, 11]
target = 8出力
3例 3
どの
入力
nums = [1, 6]
target = 20出力
2面接での聞かれ方
面接では、
- 「ソート済みの
配列と 目標の 数が あります。 あれば その 位置、 無ければ 入れる 位置を 返してください」 - 二分探索の
問題の すぐ あとに、 続きとして 出される ことが よくあります - 書き終えた
あとに 「なぜ 最後の leftが答えに なるのですか？」と 聞かれます
前のtarget 以上の
まず
段 1
まずはtarget 以上の
段 2
問題 13 のleft と right でleft <= right の
段 3
繰り返しのleft よりtarget よりright よりtarget よりleft は right の 1 つ右にleft はtarget よりleft を
ここから解答です。先に自分で書いてから読むと、考え方が残ります。
解答
Python
Python
def insert_position(
nums, target
):
left = 0
right = len(nums) - 1
while left <= right:
both = left + right
mid = both // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return leftJavaScript
JavaScript
function insertPosition(
nums, target
) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor(
(left + right) / 2
);
if (nums[mid] === target) {
return mid;
}
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}問題 13 のnums がleft の 0 を
計算量
- 時間は O(log n) です。
1 回見る たびに 範囲が およそ 半分になります - 使う
記憶は O(1) です。 持つのは left、right、midの 3 つの数だけです - 段 1 の
前から 見る 書き方は O(n) です。 答えが 「入れる位置」に 変わっても、 二分探索の 速さは そのまま使えます
よく
- 最後に
rightを返す。 繰り返しが終わった とき、 rightは「 targetより小さい 数の 最後の 位置」を 指しています。 入れる 位置は その 1 つ右なので、 leftを返します - 最後の
後ろを忘れる。 例 3 のように、 答えが 並びの 長さと 同じ 値に なることがあります。 位置は 0 から 長さまでの 範囲で 返ると 考えておきます - 空の
並びで落ちる。 先に nums[0]を見るような 書き方を すると、 空の ときに 範囲の 外を 読みます。 解答の 形なら、 空でも そのまま 0 が返ります
面接での
書き始める
「入れる
位置は、 目標以上の 数が 最初に 出てくる 位置と 言い 換えられます。 普通の 二分探索で 探し、 見つから なかった ときは 最後の 左の 端を 返します。 時間は O(log n) です。」
書き終えたら、
「例 2 の
[-3, 2, 7, 11]に 8 を入れます。 真ん中の 2 は 小さいので 左の 端を 7 の 位置へ、 次の 真ん中の 7 も 小さいので 左の 端を 11 の 位置へ 動かします。 真ん中の 11 は 大きいので 右の 端を 7 の 位置へ 戻し、 ここで 範囲が 空に なります。 左の 端は 3 で、 11 の 手前に 入れる 位置です。」