LeetCode-Python-35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 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

第一种思路：

暴力解，先插入target，然后去重，转list，排序，查找target的index即可。

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        return sorted(list(set(nums + [target]))).index(target)
        

第二种思路：

二分查找。

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

第三种思路：

按题目要求实际上就是要：

       如果target存在，找target元素的下标，因为数组已经按顺序排好，找到第一个==target元素的下标即可

       如果target不存在，如果target不插在数组末尾，那么就是第一个> target元素的下标，比如[1, 3,5]插入2之后变成[1,2,3,5]

                                     如果target应该插在数组末尾， 直接返回数组长度

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        for i, num in enumerate(nums):
            if num >= target:
                return i
        return len(nums)