链接
https://leetcode-cn.com/problems/search-insert-position/
耗时
解题:17 min
题解:3 min
题意
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
思路
二分,找到数组中大于等于目标元素的第一个值的位置,即实现 lower_bound 的功能。
时间复杂度:
O
(
l
o
g
n
)
O(logn)
O(logn)
AC代码
被注释的 return 即使用 lowe_bound
A
C
AC
AC
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int s = 0, t= nums.size();
while(s < t) {
int m = s + ((t-s) >> 1);
if(nums[m] >= target) t = m;
else s = m+1;
}
return t;
}
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)