赞
踩
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
class Solution { public int searchInsert(int[] nums, int target) { // 定义一个left为0 int left=0; //定义一个right为数组长度-1 int right=nums.length-1; //当left>right时,结束循环 while(left<=right){ //计算二分法的中间下标位置 int middle=(left+right)>>1; //如果当前(middle)位置的数组值>target,则说明target在左区间 if(nums[middle]>target){ right=middle-1; //target在左区间,[left,middle-1] }else if(nums[middle]<target){ //如果当前(middle)位置的数组值<target,则说明target在右区间 left=middle+1; //target在右区间,[middle+1,right] }else{ //nums[middle]=target return middle; } } //如果target不存在,则需要记录target将会被顺序插入的位置 //1.在数组所有元素之前 [0,-1] //2.在[left,right]中, return right+1; //大家可以画图理解,其实返回的就是middle的位置 //3.在数组所有元素之后, return right+1; return right+1; } }
class Solution {
public int searchInsert(int[] nums, int target) {
//遍历数组
for(int i=0;i<nums.length;i++){
//如果数组的元素>=target,在返回数组的下标
if(nums[i]>=target){
return i;
}
}
//如果target大于数组中的所有元素,则返回数组的长度,因为数组的下标从0开始,target将会插入到数组的最后一个位置
return nums.length;
}
}
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。