35.search insert position
难度:Easy
刷题内容
原题连接
- https://leetcode.com/problems/search-insert-position/
-
内容描述
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
思路1 **- 时间复杂度: O(lgN)*- 空间复杂度: O(1)***
由于数组是已经排序好的，这就是一个很典型的二分法
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int first = 0,last = nums.size() - 1;
while(last > (first + 1))
{
int medium = (last + first) / 2;
if(nums[medium] == target)
return medium;
else if(nums[medium] < target)
first = medium;
else
last = medium;
}
if(target > nums[last])
return last + 1;
else if((target < nums[first]) || (target == nums[first]))
return first;
else
return last;
}
};
思路2 **- 时间复杂度: O(lgN)*- 空间复杂度: O(1)***
其实这个思路也是二分法，只不过c++中已经给我们封装好了lower_bound，我们直接调用即可 代码看上去也简洁很多
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
auto pos = lower_bound(nums.begin(),nums.end(),target);
return pos - nums.begin();
}
};
