LeetCodeに毎日挑戦してみた 35. Search Insert Position（Python、Go）
はじめに
無料英単語サイトE-tanを運営中の@ishishowです。
プログラマとしての能力を上げるために毎日leetcodeに取り組み、自分なりの解き方を挙げていきたいと思います。
Leetcodeとは
leetcode.com
ソフトウェア開発職のコーディング面接の練習といえばこれらしいです。
合計1500問以上のコーデイング問題が投稿されていて、実際の面接でも同じ問題が出されることは多いらしいとのことです。
golang入門＋アルゴリズム脳の強化のためにgoとPythonで解いていこうと思います。(Pythonは弱弱だが経験あり)
10問目（問題35)
35. Search Insert Position
- 問題内容
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
（日本語訳）
個別の整数のソートされた配列とターゲット値が与えられた場合、ターゲットが見つかった場合はインデックスを返します。そうでない場合は、順番に挿入された場合のインデックスを返します。
**
Example 1:
Input: nums = [1,3,5,6], target = 5
Output: 2
Example 2:
Input: nums = [1,3,5,6], target = 2
Output: 1
Example 3:
Input: nums = [1,3,5,6], target = 7
Output: 4
Example 4:
Input: nums = [1,3,5,6], target = 0
Output: 0
Example 5:
Input: nums = [1], target = 0
Output: 0
考え方
バイナリーサーチを使って実装しました
midとターゲットを比較して二分探索していきます
範囲を絞っていき、見つかったらreturnします
- 解答コード
def searchInsert(self, nums, target): # works even if there are duplicates.
l , r = 0, len(nums)-1
while l <= r:
mid=(l+r)/2
if nums[mid] < target:
l = mid+1
else:
if nums[mid]== target and nums[mid-1]!=target:
return mid
else:
r = mid-1
return l
- Goでも書いてみます！
func searchInsert(nums []int, target int) int {
l := 0
r := len(nums) - 1
for (r >= l) {
mid := l + (r - l) / 2
if (nums[mid] == target) {
return mid
} else if (nums[mid] > target) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return l
}
Author And Source
この問題について(LeetCodeに毎日挑戦してみた 35. Search Insert Position（Python、Go）), 我々は、より多くの情報をここで見つけました https://qiita.com/ishishow/items/8bdd09e4e49ede48841b著者帰属：元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .