当前位置:   article > 正文

leetcode35.搜索插入位置

leetcode35

leetcode35.搜索插入位置

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

1.复杂度为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;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
2.暴力解法,复杂度为O(n)
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;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/凡人多烦事01/article/detail/569374
推荐阅读
相关标签
  

闽ICP备14008679号