O(n) solution


  • 0
    J
    public static  List<Integer>  countSmaller(int[] nums) {
    		 if(nums.length==0) return new ArrayList<Integer>();
    		 int[] counts=new int[nums.length];
    		 int max=Integer.MIN_VALUE;
    		 int min=Integer.MAX_VALUE;
    		 for(int i=nums.length-1;i>=0;i--){
    			 max=Math.max(max, nums[i]);
    			 min=Math.min(min, nums[i]);
    		 }
    		 int[] before=new int[max-min+2];
    		 int beforeNum=nums[nums.length-1]-min+1;
    		 for(int i=nums.length-1;i>=0;i--){
    			 int temp=nums[i]-min+1;
    			 int start=Math.min(temp, beforeNum);
    			 int end=Math.max(temp, beforeNum);			 
    			if(temp>beforeNum){ 
    				for(int j=start+1;j<=end;j++) 
    					before[j]=before[j-1];			    
    				before[temp]++;
    			}	
    			else{
    				for(int j=start;j<=end;j++)	  
    					before[j]+=1;				
    			}
    			counts[i]=before[temp-1];
    			beforeNum=end;				 
    		 }
    		 ArrayList<Integer> ans=new ArrayList<Integer>();
    		 for(int i:counts) ans.add(i);
    		 return ans;	        
    	    }
    

Log in to reply
 

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