Short Binary search version.


  • 1
    J
    public List<Integer> countSmaller(int[] nums) {
        int n=nums.length;
        List<Integer> newList=new ArrayList<Integer>();
        List<Integer> count=new ArrayList<Integer>();
        int j=0;
        for(int i=n-1;i>=0;i--){
            int index=binarySearch(newList,nums[i]);
            count.add(0,index);
            newList.add(index,nums[i]);
        }
        return count;
    }
    //find the insert index.if they are equal values, then return the first index of them
    public int binarySearch(List<Integer> newList, int target){
        int lo=0;
        int hi=newList.size()-1;
        while(lo<=hi){
            int mid=lo+(hi-lo)/2;
            if(target<=newList.get(mid)){
                hi=mid;
            }else{
                lo=mid+1;
            }
            //very important.
            if(lo==hi&&lo==mid){
    			break;
    		}
        }
        return lo;
    }

  • 0
    W

    Simple but great solution!
    I like that.
    Thanks!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.