Q35 Search Insert Position
Q35 Search Insert Position
echobingo
发布于 2018-04-25 16:41:27
发布于 2018-04-25 16:41:27
Given a sorted array 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.
You may assume no duplicates in the array.
Example 1:
Input: [1,3,5,6], 5
Output: 2Example 2:
Input: [1,3,5,6], 2
Output: 1Example 3:
Input: [1,3,5,6], 7
Output: 4Example 1:
Input: [1,3,5,6], 0
Output: 0解题思路：
实际上就是实现二分查找，时间复杂度 O(logn)
Pyhton实现：
class Solution:
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
lens = len(nums)
low = 0; high = lens - 1
while low <= high:
mid = (low + high) // 2 # 整除
if nums[mid] == target:
return mid
elif nums[mid] < target:
low = mid + 1
else:
high = mid - 1
return low
# return len([x for x in nums if x < target]) # 满足 if 条件的 target 的索引正好是生成列表的长度
a = [1,2,3,5]
b = 4
c = Solution()
print(c.searchInsert(a,b)) # 3补充：
一行代码实现，只不过时间复杂度为O(n)
return len([x for x in nums if x < target])
# 满足 if 条件的 target 的索引正好是生成列表的长度本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.02.28 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录