搜索插入位置

Question

我正在解决一个问题（leetcode 35）。我的代码为测试用例返回空值输入： [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

在我的代码下面。 我知道这个问题有许多不同的解决方案，我的解决方案不是最佳的。 但是请帮助我了解错误在哪里，而不是给出全新的解决方案。 谢谢！

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)

Answer 1

你的第一部分是正确的，使用 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)

Answer 2

您的解决方案的时间复杂度是 O（n），这还不错，但如果我们使用二叉搜索，我们可以实现更好的性能 O（log 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 low

Answer 3

看看这个！

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            

Answer 4

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if target in nums:
            return (nums.index(target))
        else:
            nums.append(target)
            nums.sort()
            return(nums.index(target))

Answer 5

如果你的 for 循环中的其他是错误的，你应该把你的 else 放在 for 循环之外。

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
            print "hello", len(nums)
            return len(nums)

但是，平分法已经包含您需要的一切。

from bisect import bisect_left
print(bisect_left([1,3,5,6],4))

作为练习，您可以尝试再次执行此练习，而不使用 index，您可能希望使用 枚举和 if else 条件。

Answer 6

Java script 上的解决方案

var searchInsert = function(nums, target) {
    let l = 0;
    let r = nums.length - 1;
    let middle = Math.floor((r + l) / 2);
    if (nums[l] > target) return 0;
    if (nums[r] < target) return r + 1;
    while (nums[middle] !== target && l < r) {
        if (nums[middle] < target) {
            l = middle + 1;
        } else {
            r = middle;
        }
        middle = Math.floor((r + l) / 2);
    }
    return middle;
};

Answer 7

我找到了最简单的解决方法。以下是我的方法。

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if target not in nums:
            nums.append(target)
            nums.sort()
        return nums.index(target)