BiruLyu
7/25/2017 - 2:56 AM

315. Count of Smaller Numbers After Self(#MergeSort).java

public class Solution {

        List<Integer> res = new LinkedList<>();
        if(nums.length==0)return res;
        res.add(0);
        TreeNode root = new TreeNode(nums[nums.length-1]);
        for(int i=nums.length-2;i>=0;i--){
            res.add(0,insert(root,nums[i]));
        }
        return res;
    }
    private int insert(TreeNode t, int v){
        if(t.val==v){
            t.repeat++;
            return t.smaller;
        }
        else{
            int sum=0;
            while(true){
                if(t.val>v){
                    t.smaller++;
                    if(t.left == null){
                        t.left = new TreeNode(v);
                        break;
                    }
                    else{
                        t=t.left;
                    }
                }
                else if(t.val<v){
                    if(t.right == null){
                        t.right = new TreeNode(v);
                        sum += (t.smaller+t.repeat);
                        break;
                    }
                    else{
                        sum += (t.smaller+t.repeat);
                        t = t.right;
                    }
                }
                else{
                    t.repeat += 1;
                    sum += t.smaller;
                    break;
                }
            }
            return sum;
        }
    }
    class TreeNode{
        TreeNode left,right;
        int repeat=1,smaller=0,val;
        public TreeNode(int val){
            this.val = val;
        }
    }
}
public class Solution {
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> res = new LinkedList<>();
        if(nums.length==0)return res;
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for(int i:nums)min = min>i ? i:min;
        int[] nums2 = new int[nums.length];
        for(int i=0;i<nums.length;i++){
            nums2[i] = nums[i]-min;
            max = max<nums2[i] ? nums2[i] : max;
        }
        int[] tree = new int[max+1];
        for(int i=nums2.length-1;i>=0;i--){
            res.add(0,get(nums2[i],tree));
            update(nums2[i]+1,tree);
        }
        return res;
    }
    private int get(int index, int[] tree){
        int sum=0;
        while(index>0){
            sum += tree[index];
            index -= (index&(~index+1));
        }
        return sum;
    }
    private void update(int index,int[] tree){
        while(index < tree.length){
            tree[index]++;
            index += (index&(~index+1));
        }
    }
}

public class Solution {
    class NumWithIndex {
        int val;
        int idx;
        int cnt;
        
        NumWithIndex (int val, int idx) {
            this.val = val;
            this.idx = idx;
            this.cnt = 0;
        }
    }
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> res = new ArrayList<>();
        if (nums == null || nums.length < 1) return res;
        int len = nums.length;
        NumWithIndex[] numsIdx = new NumWithIndex[len];
        for (int i = 0; i < len; i++) {
            numsIdx[i] = new NumWithIndex(nums[i], i);
        }
        NumWithIndex[] helper = new NumWithIndex[len];
        mergeSort(numsIdx, helper, 0, len - 1);
        int[] temp = new int[len];
        for (NumWithIndex num : numsIdx) {
        	temp[num.idx] = num.cnt;
        	//res.add(num.idx, num.cnt);
        }
        for (int cnt : temp) {
        	res.add(cnt);
        }
        return res;
    }
    
    private void mergeSort(NumWithIndex[] nums, NumWithIndex[] helper, int start, int end) {
        if (end <= start) return;
        int mid = start + (end - start) / 2;
        mergeSort(nums, helper, start, mid);
        mergeSort(nums, helper, mid + 1, end);
        
        mergeAndCount(nums, helper, start, end);
    }
    
    private void mergeAndCount(NumWithIndex[] nums, NumWithIndex[] helper, int start, int end) {
        int mid = start + (end - start) / 2;
        int i = start;
        int j = mid + 1;
        int count = 0;
        while (i <= mid) {
            if (j <= end && nums[i].val > nums[j].val) {
                count++;
                j++;
            } else {
                nums[i].cnt += count;
                i++;
            }
        }
        
        // merge
        for (i = start; i <= end; i++) {
            helper[i] = nums[i];
        }
        i = start;
        j = mid + 1;
        int k = start;
        while (i <= mid && j <= end) {
            if (helper[i].val <= helper[j].val) {
                nums[k++] = helper[i++];
            } else {
                nums[k++] = helper[j++];
            }
        }
        while (i <= mid) {
            nums[k++] = helper[i++];
        }
    }
}