JAVA 牛牛

35. 搜索插入位置

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

题目 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)
  • 如果你也发现了，请为自己点赞，顺便为小牛点赞👍支持
  • 如果发现在别处也有类似的例题，请在下面👇评论区告诉小牛
Search