1. Count of Smaller Numbers After Self

You are given an integer array nums and you have to return a new counts array. The counts array has the property wherecounts[i]is the number of smaller elements to the right ofnums[i].

Example:
Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Return the array[2, 1, 1, 0].

BST Solution,
class TreeNode {

    int val;
    int less = 0;
    int dup  = 1;
    TreeNode left, right;

    public TreeNode(int val) {
        this.val = val;
    }
}

public class Solution {
    public List<Integer> countSmaller(int[] nums) {

        List<Integer> ans = new ArrayList<>();

        TreeNode root = null;

        for(int i = nums.length - 1; i >= 0; i --)
            root = insert(nums[i], root, ans, 0);

        return ans;
    }

    public TreeNode insert(int num, TreeNode node, List<Integer> ans, int pre) {

        if(node == null){
            node = new TreeNode(num);
            ans.add(0, pre);
        }
        else if(node.val == num){
            node.dup ++;
            ans.add(0, pre + node.less);
        }
        else if(num < node.val){
            node.less ++;
            node.left = insert(num, node.left, ans, pre);
        }
        else{
            node.right = insert(num, node.right, ans, pre + node.less + node.dup);
        }
        return node;
    }
}

merge sort is too complex.

2. Reverse Pairs

Given an arraynums, we call(i, j)animportant reverse pairifi < jandnums[i] > 2*nums[j].

You need to return the number of important reverse pairs in the given array.

Example1:

Input
: [1,3,2,3,1]

Output
: 2

Example2:

Input
: [2,4,3,5,1]

Output
: 3

BST Solution, accepted days ago, but nowdays TLE

class TreeNode {

    int val;
    int less = 0;
    int dup  = 1;
    TreeNode left, right;

    public TreeNode(int val) {
        this.val = val;
    }

}

public class Solution {


    public int reversePairs(int[] nums) {

        TreeNode root = null;
        int count = 0;

        for(int i = nums.length - 1; i >= 0; i --) {


            count+= search(nums[i]/ 2.0, root);
            root  = insert(nums[i], root);
        }

        return count;
    }

    public int search(double num, TreeNode node) {

        if (node == null) {
            return 0;
        }
        else if (num == node.val) {
            return node.less;

        } else if (num < node.val) {
            return search(num, node.left);

        } else {//num > node.val
            return node.less + node.dup + search(num, node.right);
        }

    }


    public TreeNode insert(int num, TreeNode node) {

        if(node == null){
            node = new TreeNode(num);
        }
        else if(node.val == num){
            node.dup ++;
        }
        else if(num < node.val){

            node.less ++;
            node.left = insert(num, node.left);
        }
        else{

            node.right = insert(num, node.right);
        }

        return node;
    }
}

public class Solution {
    public int reversePairs(int[] nums) {

        return mergeSort(nums, 0, nums.length - 1);
    }

    public int mergeSort(int[] nums, int s, int e) {

        if(s >= e) return 0;

        int mid = (s + e) / 2;

        int count = mergeSort(nums, s, mid) + mergeSort(nums, mid + 1, e);

        for(int i = s, j = mid + 1; i <= mid; i ++) {

            while(j <= e && nums[i] / 2.0 > nums[j]) j ++;
            count += j - (mid + 1);
        }
        Arrays.sort(nums, s, e + 1);//这一步其实有问题！但为了简单期间
        return count;
    }
}