问题描述
https://leetcode.com/problems/search-insert-position/
解决思路一
比较简单，直接遍历数组，不断地将小于target的元素的下标加1给target就可以。
代码一
class Solution {
public int searchInsert(int[] nums, int target) {
//corner case
if(nums.length == 0 || nums == null) return 0;
int index = 0;
for(int i = 0; i < nums.length; i++){
if(nums[i] < target){
index = i + 1;
}
}
return index;
}
}
复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(1)
解决思路二
有序，找数，首推二分法。唯一需要处理的是如果找不到怎么办。其实也只要分三种情况讨论：（target)start(target)end(target)，如果找不到，target只会出现在这三种位置上。
代码二
class Solution {
public int searchInsert(int[] nums, int target) {
//corner case
if(nums.length == 0 || nums == null) return 0;
int start = 0;
int end = nums.length - 1;
while(start + 1 < end){
int mid = (end - start) / 2 + start;
if(nums[mid] == target){
return mid;
}else if(nums[mid] > target){
end = mid;
}else{
start = mid;
}
}
//if target does not exist in the array
if(target <= nums[start]) return start;
else if(target <= nums[end]) return end;
else return end + 1;
}
}
复杂度分析
- 时间复杂度：O(log(n))
- 空间复杂度：O(1)
