share my java solution!


  • 0
    T
    class Solution {
        public List<Integer> countSmaller(int[] nums) {
            if(nums==null || nums.length<1){
                return new ArrayList<>();
            }
            int[] count = new int[nums.length];
            count[nums.length-1]=0;
            List<Integer> list = new ArrayList<>();
            list.add(nums[nums.length-1]);
            for(int i=nums.length-2;i>=0;i--){
                int ele = nums[i];
                int index = binarySearch(list,ele);
                count[i] = index;
                list.add(index,ele);
            }
            
            list = new ArrayList<>();
            for(int ele:count){
                list.add(ele);
            }
            return list;
        }
        
        public int binarySearch(List<Integer> list,int ele){
            int i=0;
            int j=list.size();
            while(i<j){
                int mid=(i+j)>>>1;
                if(list.get(mid)>=ele){
                    j=mid;
                }else{
                    i=mid+1;
                }
            }
            
            return i;
        }
    }
    
    

Log in to reply
 

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