题目描述
题解
两次遍历
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
for(int i = 0; i < nums.size(); i++) {
if(nums[i] == target) return i;
}
for(int i = 0; i < nums.size(); i++) {
if(nums[i] > target) {
return i;
}
}
return nums.size();
}
};
时间复杂度为，空间复杂度为
。
一次遍历
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int i;
for(i = 0; i < nums.size(); i++) {
if(nums[i] >= target) break;
}
return i;
}
};
时间复杂度为，空间复杂度为
。
二分法
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int low = 0, mid = 0;
int high = nums.size();
while(low < high) {
mid = low + (high - low) / 2;
if(nums[mid] > target) {
high = mid;
}
else if(nums[mid] < target) {
low = mid + 1;
}
else return mid;
}
return low;
}
};
时间复杂度为，空间复杂度为
。
