35. 搜索插入位置

  • 难度简单
  • 本题涉及算法二分查找
  • 思路二分查找 暴力 目标值插入数组
  • 类似题型:

题目 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

方法一 二分查找

  • 复杂度分析
    • 时间复杂度 $O(logN)))$ ,这里 $N$ 是数组的长度,每一次都将问题的规模缩减为原来的一半,因此时间复杂度是对数级别的
    • 空间复杂度 $O(1)$
      class Solution(object):
        def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left , right = 0, len(nums)
        while left < right:
            mid = left + (right - left)/2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid
        return left
      

方法二 暴力遍历

  • 复杂度分析
    • 时间复杂度 $O(logN)))$ ,这里 $N$ 是数组的长度,最差情况下遍历 目标值>数组最后一个值
    • 空间复杂度 $O(1)$
      class Solution:
        def searchInsert(self, nums: List[int], target: int) -> int:
        if not nums:
            return 0
        if nums[-1] < target:
            return len(nums)
        for i in range(len(nums)):
            if nums[i] >= target:
                return i
      
      class Solution {
        public int searchInsert(int[] nums, int target) {
        int len = nums.length;
        int ans = 0;
        if (len == 0){
            return 0;
        }
        if (nums[len-1] < target) {
            return len;
        }
      
        for (int i = 0;i<len;i++) {
            if (nums[i] >= target) {
                ans = i;
                break;
            }
        }
        return ans;
        }
      }
      

      方法三 目标值插入数组后在查找对于位置(提供了一个新思路)

  • 解题思路
    • 目标值插入数组中
    • 排序后在查询对于目标值的位置
  • 复杂度分析
    • 时间复杂度 $O(logN)))$ ,这里 $N$ 是数组的长度,最差情况下遍历 目标值>数组最后一个值
    • 空间复杂度 $O(1)$
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        # 不管这个数在不在里面,直接append
        nums.append(target)
        # 然后再排序
        nums.sort()
        # 最后返回查找的index
        return nums.index(target)

  • 如果你也发现了,请为自己点赞,顺便为小牛点赞👍支持
  • 如果发现在别处也有类似的例题,请在下面👇评论区告诉小牛