share my java merge sort solution!


  • 0
    T
    class Solution {
        class myInteger{
            int val;
            int index;
            int count;
            myInteger(int val,int index){
                this.val = val;
                this.index = index;
                count=0;
            }
        }
        public List<Integer> countSmaller(int[] nums) {
            if(nums==null || nums.length<1){
                return new ArrayList<>();
            }
            myInteger[] myNums = new myInteger[nums.length];
            for(int i=0;i<nums.length;i++){
                myNums[i] = new myInteger(nums[i],i);
            }
            
            int p=0;
            merger(myNums,0,nums.length-1);
            int[] count = new int[nums.length];
            
            for(int i=0;i<myNums.length;i++){
                //System.out.println(myNums[i].index);
                count[myNums[i].index] = myNums[i].count;
            }
            
            List<Integer> list = new ArrayList<>();
            for(int ele:count){
                list.add(ele);
            }
            return list;
        }
        
        public void merger(myInteger[] myNums,int start,int end){
            if(start>=end){
                return;
            }
            int mid = (start+end)>>>1;
            merger(myNums,start,mid);
            merger(myNums,mid+1,end);
            int j = mid+1;
            for(int i=start;i<=mid;i++){
                while(j<=end&&myNums[i].val<=myNums[j].val){
                    j++;
                }
                myNums[i].count+=end-j+1;
            }
            mergerHelper(myNums,start,mid,end);
        }
        
        public void mergerHelper(myInteger[] myNums,int start,int mid,int end){
            myInteger[] copy = new myInteger[end-start+1];
            int i = start;
            int j = mid+1;
            int p = 0;
            while(i<=mid&&j<=end){
                if(myNums[i].val>=myNums[j].val){
                    copy[p++] = myNums[i++];
                }else{
                    copy[p++] = myNums[j++];
                }
            }
            
            while(i<=mid){
                copy[p++]=myNums[i++];
            }
            while(j<=end){
                copy[p++] = myNums[j++];
            }
            
            i = start;
            p = 0;
            while(p<copy.length){
                myNums[i++] = copy[p++];
            }
        }
    }
    

Log in to reply
 

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