多味的LeetCode --- 35. 搜索插入位置

冷不防 2022-11-11 14:59 110阅读 0赞

**题目描述：**

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

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

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

--------------------

**解题思路1:**

分以下几种情况：

1.  目标值小于数组中的第一个元素；
2.  目标值大于数组中最后一个元素；
3.  数组中存在与目标值相等的元素；
4.  目标值介于数组元素之间；

--------------------

**代码1：**

class Solution:
        def searchInsert(self, nums, target):
            size = len(nums)
            if target > nums[size-1]:
                return size
            if target < nums[0]:
                return 0
            for i in range(size):
                if target == nums[i]:
                    return i
                if target > nums[i] and target < nums[i+1]:
                    return i + 1

--------------------

**解题思路2:**

顺序查找

--------------------

**代码2：**

class Solution(object):
        def searchInsert(self, nums, target):
            size = len(nums)
            for i in range(size):
                if nums[i] >= target:
                    return i
            return size

--------------------

**解题思路3:**

二分查找

--------------------

**代码3：**

class Solution(object):
        def searchInsert(self, nums, target):
            left, right = 0, len(nums)
            while(left < right):
                mid = (left + right) // 2
                if target <= nums[mid]:
                    right = mid
                else:
                    left = mid + 1
            return left

--------------------

**题目来源：**

[https://leetcode-cn.com/problems/search-insert-position][https_leetcode-cn.com_problems_search-insert-position]

[https_leetcode-cn.com_problems_search-insert-position]: https://leetcode-cn.com/problems/search-insert-position