- 难度:
简单
- 本题涉及算法:
二分查找
- 思路:
二分查找
暴力
目标值插入数组
- 类似题型:
题目 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)
- 如果你也发现了,请为自己点赞,顺便为小牛点赞👍支持
- 如果发现在别处也有类似的例题,请在下面👇评论区告诉小牛
PREVIOUS46. 全排列