每日一题2
先看题目要求。
属于简答题，那么一开始我自己写就很直接暴力，循环一边就好了，管他什么效率。代码如下：
package K;
public class Insert {
public int searchInsert(int[] A, int target) {
// write your code here
int i = 0;
for(; i < A.length; i++){
if(target == A[i]){
return i;
}
else if(i >= 1 && A[i] > target && target > A[i-1]){
return i;
}
else if(i == A.length-1 && target > A[i]){
return i+1;
}
}
return 0;
}
public static void main(String[] args){
int[] nums = {2,4,6,1,8};
Insert i = new Insert();
int result;
result = i.searchInsert(nums, 4);
System.out.println(result);
}
}
OK，代码没问题，能跑，但不是最优解，在网上看了一下，发现自己有一个盲点，没有注意到数组是有序的！这个很关键，如果数组有序，可以直接使用二分法即可实现，提高不少效率。代码如下：
package K;
public class Solution {
public int searchInsert(int[] A, int target) {
int mid;
int lo = 0;
int hi = A.length - 1;
while (lo <= hi) {
mid = lo + (hi - lo)/ 2;
if (A[mid] == target) {
return mid;
} else if (A[mid] < target){
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return lo;
}
}
public static void main(String[] args){
int[] nums = {2,4,6,1,8};
Insert i = new Insert();
int result;
result = i.searchInsert(nums, 4);
System.out.println(result);
}
}
切记切记：这种二分法思想！！！
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2018-11-09，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读