给定一个排序的整数数组 nums 和一个整数目标值 target ,请在数组中找到 target ,并返回其下标。
如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:输入: nums = [1,3,5,6], target = 5 输出: 2
示例 2:输入: nums = [1,3,5,6], target = 2 输出: 1
示例 3:输入: nums = [1,3,5,6], target = 7 输出: 4
示例 4:输入: nums = [1,3,5,6], target = 0 输出: 0
示例 5:输入: nums = [1], target = 0 输出: 0
提示:1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为无重复元素的升序排列数组
-104 <= target <= 104
注意:本题与主站 35 题相同:
1、二分查找;时间复杂度O(log(n)),空间复杂度O(1)
func searchInsert(nums []int, target int) int {
low, high := 0, len(nums)-1
for low <= high {
mid := (low + high) / 2
switch {
case nums[mid] < target:
low = mid + 1
case nums[mid] > target:
high = mid - 1
default:
return mid
}
}
return low
}
2、顺序查找;时间复杂度O(n),空间复杂度O(1)
func searchInsert(nums []int, target int) int {
i := 0
for i < len(nums) && nums[i] < target {
if nums[i] == target {
return i
}
i++
}
return i
}
3、顺序查找;时间复杂度O(n),空间复杂度O(1)
func searchInsert(nums []int, target int) int {
for i := 0; i < len(nums); i++ {
if nums[i] >= target {
return i
}
}
return len(nums)
}
Easy题目,题目同leetcode 35.搜索插入位置
页面更新:2024-06-07
本站资料均由网友自行发布提供,仅用于学习交流。如有版权问题,请与我联系,QQ:4156828
© CopyRight 2020-2024 All Rights Reserved. Powered By 71396.com 闽ICP备11008920号-4
闽公网安备35020302034903号