美文网首页
Find First and Last Position of

Find First and Last Position of

作者: 海生2018 | 来源:发表于2019-10-14 14:25 被阅读0次

    Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

    Your algorithm's runtime complexity must be in the order of O(log n).

    If the target is not found in the array, return [-1, -1].

    Example 1:

    Input: nums = [5,7,7,8,8,10], target = 8
    Output: [3,4]
    

    Example 2:

    Input: nums = [5,7,7,8,8,10], target = 6
    Output: [-1,-1]
    

    Solution

    class Solution {
        public int[] searchRange(int[] nums, int target) {
            if(nums==null) return null;
            return bs(nums,target);
        }
        private int[] bs(int[] nums,int t){
            int n=nums.length;
            int s=-1,e=-1;
            int l=0,r=n-1;
            while(l<=r){
                int m=l+(r-l)/2;
                if(t<nums[m]){
                    r=m-1; 
                }else if(t>nums[m]){
                    l=m+1;
                }else{
                    s=m;
                    e=m;
                    int tmp=bsRange(nums,t,l,m-1,true);
                    s=tmp<0?s:tmp;
                    tmp=bsRange(nums,t,m+1,r,false);
                    e=tmp<0?e:tmp;
                    return new int[]{s,e};
                }
            }
            return new int[]{s,e};
        }
    
        private int bsRange(int[] nums,int t,int l,int r,boolean f){
            int idx=-1;
            while(l<=r){
                int m=l+(r-l)/2;
                if(t<nums[m]){
                    r=m-1;
                }else if(t>nums[m]){
                    l=m+1;
                }else{
                    idx=m;
                    if(f){
                        r=m-1;   
                    }else{
                        l=m+1;
                    }
                }
            }
            return idx;
        }
    }
    

    时间O(logn)
    空间O(1)

    既然要求logn时间那得是二分查找了,我的思路是先用二分法找到他在不在,在的话将他作为分割点,分成两个子数组,对这两个子数组进行二分查找,在找到等于时不返回,继续遍历直到结束,使用idx记录最后一个匹配的位置。令我没想到的是竟然打败了100%的人。标准答案是用一个方法查找左右,我个人理解先查在不在应该是可以剪枝的。

    相关文章

      网友评论

          本文标题:Find First and Last Position of

          本文链接:https://www.haomeiwen.com/subject/fidrmctx.html