搜索插入位置
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
二分查找法
题目要求“必须使用时间复杂度为 O(log n) 的算法”,因此,必然会想到二分查找算法。此题在标准二分查找的基础上增加了插入功能,如何实现呢?
假定插入位置为pos,则必然有nums[pos-1] < target < nums[pos],成立
假定元素在pos处存在,则必有nums[pos-1] < target == nums[pos]
合并为:nums[pos-1] < target <= nums[pos]
综上所述,我们得出最终目标:「在一个有序数组中找第一个大于等于 target的下标」文章来源:https://www.toymoban.com/news/detail-794245.html
复杂度分析
时间复杂度:O(logn),n为nums的长度,二分查找算法时间复杂度为O(logn)。
空间复杂度:O(1),仅用常量空间存储变量。文章来源地址https://www.toymoban.com/news/detail-794245.html
Swift
func searchInsert(_ nums: [Int], _ target: Int) -> Int {
let cnt = nums.count
var leftIdx = 0, rightIdx = cnt-1
//为啥是cnt,因为可以少处理边界情况,比如target比所有元素都大时,结果就是cnt
var ans = cnt
while leftIdx <= rightIdx {
let mid = (leftIdx + rightIdx) >> 1
if target <= nums[mid] {
rightIdx = mid - 1
ans = mid
}else {
leftIdx = mid + 1
}
}
return ans + 1
}
OC
//由于要考虑到插入,位置为pos,有nums[pos-1] < target <= nums[pos],
//因此,问题转换为[找出第一个大于等于target的元素所在的位置]
- (NSInteger)searchInsert:(NSArray *)nums
target:(NSInteger)target {
NSInteger cnt = nums.count;
NSInteger left = 0, right = cnt - 1;
NSInteger ans = cnt;//赋值为cnt可减少边界情况处理,如target大于所有元素,那么就在最后一个位置插入
while (left <= right) {
NSInteger mid = (left + right) >> 1;
if (target <= [nums[mid] integerValue]) {
ans = mid;
right = mid - 1;
}else {
left = mid + 1;
}
}
return ans;
}
到了这里,关于LeetCode 35. 搜索插入位置的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!