Leetcode 搜索插入位置
Leetcode 搜索插入位置
Categories:
搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 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
解题思路
二分查找
求出最小和最大索引的取整中间值, 判断该索引的value是否等于target, 如果相等返回索引位置
如果value大于target, 则查找的目标在中间索引值左侧, 将现在的最大索引值重置为中间值
如果value小于target, 则查找的目标在中间索引值右侧, 将现在的最小索引值重置为中间值
重新取中间索引值继续比较, 直到找到或找不到退出
则元素应该插入的位置为最后最小索引值+1
Answer
1#
2# @lc app=leetcode.cn id=35 lang=python3
3#
4# [35] 搜索插入位置
5#
6
7# @lc code=start
8class Solution:
9 def searchInsert(self, nums: List[int], target: int) -> int:
10 m = 0
11 n = len(nums)-1
12 while m <= n:
13 k = (m + n) // 2
14 if target == nums[k]:
15 return k
16 elif target > nums[k]:
17 m = k + 1
18 else:
19 n = k - 1
20 return n+1
21# @lc code=end
Accepted
62/62 cases passed (32 ms)
Your runtime beats 97.37 % of python3 submissions
Your memory usage beats 7.14 % of python3 submissions (14.3 MB)