搜索插入位置
搜索插入位置
提问于 2019-01-02 14:07:28
我正在解决一个问题(代码35)。我的代码为测试用例输入返回null : 1,3,5,6，7。找不到错误。
给定排序数组和目标值，如果找到目标，则返回索引。如果没有，则返回如果按顺序插入的索引。
您可以假设数组中没有重复项。
Example 1:
Input: [1,3,5,6], 5
Output: 2
Example 2:
Input: [1,3,5,6], 2
Output: 1
Example 3:
Input: [1,3,5,6], 7
Output: 4
Example 4:
Input: [1,3,5,6], 0
Output: 0在我的代码下面。我知道这个问题有很多不同的解决方案，我的解决方案也不是最优的。但是，请帮助我理解bug在哪里，而不是给出一个全新的解决方案。谢谢!
class Solution(object):
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
try:
return nums.index(target)
except:
for i in range(len(nums)):
print i
if nums[i] - target > 0:
return i
else:
print "hello", len(nums)
return len(nums)回答 7
Stack Overflow用户
回答已采纳
发布于 2019-01-02 14:17:20
您的第一部分是正确的，使用list.index并捕获异常。然而，你的第二部分(没有打印)
for i in range(len(nums)):
if nums[i] - target > 0:
return i # return if True
else:
return len(nums) # return if False这意味着for循环的第一次迭代无论如何都会返回。
您需要将else块从for循环中删除；如下所示：
def searchInsert(self, nums, target):
try:
return nums.index(target)
except IndexError: # best to use explicit except
for index, value in enumerate(nums): # more pythonic than range(len(nums))
if value > target:
return index
return len(nums)Stack Overflow用户
发布于 2020-06-10 12:46:29
您的解决方案的时间复杂性是O(n)，这并不坏，但是如果我们使用二进制搜索，我们可以获得更好的性能O(原木n)。
class Solution:
def searchInsert(self, array: List[int], target: int) -> int:
low = 0
high = len(array)
while low < high:
middle = (high + low) // 2
if array[middle] == target:
return middle
if array[middle] < target:
low = middle + 1
if array[middle] > target:
high = middle - 0
return lowStack Overflow用户
发布于 2019-01-16 18:56:22
看看这个！
class Solution:
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
nums.append(target)
nums.sort()
for i,j in enumerate(nums):
if target == j:
return i 页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/54007783
复制相关文章
相似问题
腾讯云开发者
