https://leetcode-cn.com/problems/search-insert-position/
最直接的思路，需要处理的分支情况很多。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int searchInsert(int[] nums, int target) {
if(target<nums[0]){
return 0;
}
if(target>nums[nums.length-1]){
return nums.length;
}
if(target==nums[nums.length-1]){
return nums.length-1;
}
for(int i=0;i<nums.length-1;i++){
if(nums[i]==target){
return i;
}else if(nums[i]<target && nums[i+1]>target){
return i+1;
}
}
return 0;
}
}
|
简化一下代码中的 case，可以得到如下：
1
2
3
4
5
6
7
8
9
| class Solution {
public int searchInsert(int[] nums, int target) {
for(int i=0;i<nums.length;i++){
if(target<=nums[i])
return i;
}
return nums.length;
}
}
|
其实这是一个查找问题，尝试使用二分查找(Binary Search)解决一下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int searchInsert(int[] nums, int target) {
int low=0;
int high=nums.length-1;
while(low<=high){
int middle=(low+high)/2;
if(target==nums[middle])
return middle;
if(target<nums[middle]){
high=middle-1;
}else{
low=middle+1;
}
}
return low;
}
}
|