35.搜索插入位置

描述

給定一個排序數(shù)組和一個目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會被按順序插入的位置。

你可以假設(shè)數(shù)組中無重復(fù)元素。

示例

示例 1:

輸入: [1,3,5,6], 5 輸出: 2

示例 2:

輸入: [1,3,5,6], 2 輸出: 1

示例 3:

輸入: [1,3,5,6], 7 輸出: 4

示例 4:

輸入: [1,3,5,6], 0 輸出: 0

思路

對于不存在的情況， 我們只需要在數(shù)組里面找到最小的一個值大于 value 的 index ， 這個 index 就是我們可以插入的位置。 譬如 [1, 3, 5, 6] ， 查找 2 ， 我們知道 3 是最小的一個大于 2 的數(shù)值， 而 3 的 index 為 1 ， 所以我們需要在 1 這個位置插入 2 。 如果數(shù)組里面沒有值大于 value ， 則插入到數(shù)組末尾。

class Solution:def searchInsert(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""low = 0high = len(nums) - 1while low <= high:mid = low + (high - low) // 2if nums[mid] == target:return midelif nums[mid] < target:low = mid + 1else:high = mid - 1return low

GitHub地址：https://github.com/protea-ban/LeetCode

轉(zhuǎn)載于:https://www.cnblogs.com/banshaohuan/p/9771007.html

總結(jié)

以上是生活随笔為你收集整理的LeetCode35.搜索插入位置的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。