LeetCode 315 - Count of Smaller Numbers After Self


TODO: https://leetcode.com/problems/count-of-smaller-numbers-after-self/discuss/76729/onlogn-divide-and-conquer-java-solution-based-on-bit-by-bit-comparison
Related: [LintCode] Count of Smaller Number before itself
Count Inversions in an array
https://leetcode.com/discuss/73233/complicated-segmentree-solution-hope-to-find-a-better-one
You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[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].
https://yijiajin.github.io/leetcode/2016/12/22/Leetcode-Segment-Tree-Binary-Index-Tree/
Naive BinarySearch solution: O(nlogn) 55s
For each n in the nums, binary search its index, from the end of nums to the start, and copy the result into another list.
public class Solution {
    public List<Integer> countSmaller(int[] nums) {
        Integer[] ans = new Integer[nums.length];
        List<Integer> sorted = new ArrayList<Integer>();
        for(int i = nums.length - 1; i >= 0; i--){
            int index = findIndex(sorted, nums[i]);
            ans[i] = index;
            sorted.add(index, nums[i]); // bad
        } // for i
        return Arrays.asList(ans);
    } // smaller
    
    public int findIndex(List<Integer> sorted, int cur){
        if(sorted.size() == 0)  return 0;
        int start = 0, end = sorted.size() - 1;
        if(sorted.get(end) < cur)   return end + 1;
        if(sorted.get(start) >= cur) return start;
        while(start < end){
            int mid = start + (end - start)/2;
            if(sorted.get(mid) < cur){
                start = mid + 1;
            }else{
                end = mid;
            }
        }
        if (sorted.get(start) >= cur) return start;
        return end;
    } // findIndex
}
X.  二叉搜索树 （Binary Search Tree)
树节点TreeNode记录下列信息：
  • 元素值：val
  • 小于该节点的元素个数：leftCnt
  • 节点自身的元素个数：cnt
  • 左孩子：left
  • 右孩子：right
从右向左遍历nums，在向BST插入节点时顺便做统计
http://bookshadow.com/weblog/2015/12/06/leetcode-count-of-smaller-numbers-after-self/
When building the BST, maintain a record of the total number on it’s left (smaller numbers), and duplicate numbers. When insertign new numbers, the answer should be the add of that two number of all nodes that turns right(not the number of itself).
https://medium.com/@timtim305/leetcode-315-count-of-smaller-numbers-after-self-be529cdfe148
This solution runs in O(n log n) in the average case. However, if the nums array is given to us sorted in ascending or descending order, that run time degenerates into O(n)². We can fix this by using a self-balancing BST (AVL tree or a red-black tree) and retaining the same logic.

https://kennyzhuang.gitbooks.io/algorithms-collection/content/count_of_smaller_numbers_after_self.html
class TreeNode {
    TreeNode left; 
    TreeNode right;
    int val;
    int count = 1;
    public TreeNode(int val) {
        this.val = val;
    }
}
   public List<Integer> countSmaller(int[] nums) {
        List<Integer> res = new ArrayList<>();
        if(nums == null || nums.length == 0) return res;
        TreeNode root = new TreeNode(nums[nums.length - 1]);
        res.add(0);
        for(int i = nums.length - 2; i >= 0; i--) {
            int count = insertNode(root, nums[i]);
            res.add(count);
        }
        Collections.reverse(res);
        return res;
    }

    public int insertNode(TreeNode root, int val) {
        int thisCount = 0;
        while(true) {
            if(val <= root.val) {
                root.count++;
                if(root.left == null) {
                    root.left = new TreeNode(val); break;
                } else {
                    root = root.left;
                }
            } else {
                thisCount += root.count;
                if(root.right == null) {
                    root.right = new TreeNode(val); break;
                } else {
                    root = root.right;
                }
            }
        }
        return thisCount;
    }
https://discuss.leetcode.com/topic/31405/9ms-short-java-bst-solution-get-answer-when-building-bst
Every node will maintain a val sum recording the total of number on it's left bottom side, dupcounts the duplication. For example, [3, 2, 2, 6, 1], from back to beginning,we would have:
                1(0, 1)
                     \
                     6(3, 1)
                     /
                   2(0, 2)
                       \
                        3(0, 1)
When we try to insert a number, the total number of smaller number would be adding dup and sum of the nodes where we turn right. for example, if we insert 5, it should be inserted on the way down to the right of 3, the nodes where we turn right is 1(0,1), 2,(0,2), 3(0,1), so the answer should be (0 + 1)+(0 + 2)+ (0 + 1) = 4
if we insert 7, the right-turning nodes are 1(0,1), 6(3,1), so answer should be (0 + 1) + (3 + 1) = 5
runtime could be O(n^2) when processing input like n, n-1, ..., 2, 1. I think the test cases are not good enough.
There is no need for considering the duplication elements. See the code below which is referred from: http://www.cnblogs.com/grandyang/p/5078490.html
class TreeNode{
        int smallCount;
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int count, int val){
            this.smallCount = count;
            this.val = val;
        }
    }
    
    public List<Integer> countSmaller(int[] nums) {
        TreeNode root = null;
        Integer[] ret = new Integer[nums.length];//\\
        if(nums == null || nums.length == 0) return Arrays.asList(ret);
        for(int i=nums.length-1; i>=0; i--){
            root = insert(root, nums[i], ret, i, 0);
        }
        return Arrays.asList(ret);//\\
    }
    
    public TreeNode insert(TreeNode root, int val, Integer[] ans, int index, int preSum){
        if(root == null){
            root = new TreeNode(0, val);
            ans[index] = preSum;
        }
        else if(root.val>val){
            root.smallCount++;
            root.left = insert(root.left, val, ans, index, preSum);
        }
        else{
            root.right = insert(root.right, val, ans, index, root.smallCount + preSum + (root.val<val?1:0));//only adding 1 on preSum if root.val is only smaller than val
        }
        return root;
    }

class Node{
    int val, leftSum = 0, count = 0;
    Node left, right;
    public Node(int val){
        this.val = val;
    }
}
public List<Integer> countSmaller(int[] nums) {
    Integer[] count = new Integer[nums.length];
    if(nums.length == 0){
        return Arrays.asList(count);
    }
    Node root = new Node(nums[nums.length - 1]);
    for(int i = nums.length - 1; i >= 0; i--){
        count[i] = insert(root, nums[i]);
    }
    return Arrays.asList(count);
}
private int insert(Node node, int num){
    int sum = 0;
    while(node.val != num){
        if(node.val > num){
            if(node.left == null) node.left = new Node(num);
            node.leftSum++;
            node = node.left;
        }else{
            sum += node.leftSum + node.count;
            if(node.right == null) node.right = new Node(num);
            node = node.right;
        }
    }
    node.count++;
    return sum + node.leftSum;
}
https://discuss.leetcode.com/topic/31422/easiest-java-solution
Traverse from nums[len - 1] to nums[0], and build a binary search tree, which stores:
  1. val: value of nums[i]
  2. count: if val == root.val, there will be count number of smaller numbers on the right
 public List<Integer> countSmaller(int[] nums) {
  List<Integer> res = new ArrayList<>();
  if(nums == null || nums.length == 0) return res;
  TreeNode root = new TreeNode(nums[nums.length - 1]);
  res.add(0);
  for(int i = nums.length - 2; i >= 0; i--) {
   int count = insertNode(root, nums[i]);
   res.add(count);
  }
  Collections.reverse(res);
  return res;
 }

 public int insertNode(TreeNode root, int val) {
  int thisCount = 0;
  while(true) {
   if(val <= root.val) {
    root.count++;
    if(root.left == null) {
     root.left = new TreeNode(val); break;
    } else {
     root = root.left;
    }
   } else {
    thisCount += root.count;
    if(root.right == null) {
     root.right = new TreeNode(val); break;
    } else {
     root = root.right;
    }
   }
  }
  return thisCount;
 }
}

class TreeNode {
 TreeNode left; 
 TreeNode right;
 int val;
 int count = 1;
 public TreeNode(int val) {
  this.val = val;
 }
}
https://discuss.leetcode.com/topic/55730/my-bst-solution-with-detailed-explanation
Basically, the idea is very easy. We traverse the array backwards meanwhile build a BST (AVL, RB-tree... whatever). The key is how to get how many nodes in tree smaller than current node. The code as below says everything.
Here is the solution but getting TLE . You know why, thats because headset.size() is O(N) surprisngly. SO we cant use this Treeset/Treemap
public List<Integer> countSmaller(int[] nums) {
     if(nums==null || nums.length==0)
      return new ArrayList<Integer>();
     List<Integer> l =new ArrayList<Integer>();
     
     TreeSet<Integer> s=new TreeSet<>();
     s.add(nums[nums.length-1]);
     l.add(0);
     for( int i=nums.length-2;i>=0;i--){
      SortedSet<Integer> s1=s.headSet(nums[i]);
      l.add(s1.size());
      s.add(nums[i]);
      
     }
     Collections.reverse(l);
  return l;
}
    public List<Integer> countSmaller(int[] nums) {
        Integer[] counter = new Integer[nums.length];
        TreeSet<Integer> tree = new TreeSet<>(
            (a, b) -> (Integer.compare(a, b) == 0) ? -1 : Integer.compare(a, b));
        for (int i = nums.length - 1; i >= 0; i--) {
            tree.add(nums[i]);
            counter[i] = tree.headSet(nums[i]).size(); // Here is the key!!!
        }
        return Arrays.asList(counter);
    }
    class Node {
        Node left, right;
        int val, sum, dup = 1;
        public Node(int v, int s) {
            val = v;
            sum = s;
        }
    }
    public List<Integer> countSmaller(int[] nums) {
        Integer[] ans = new Integer[nums.length];
        Node root = null;
        for (int i = nums.length - 1; i >= 0; i--) {
            root = insert(nums[i], root, ans, i, 0);
        }
        return Arrays.asList(ans);
    }
    private Node insert(int num, Node node, Integer[] ans, int i, int preSum) {
        if (node == null) {
            node = new Node(num, 0);
            ans[i] = preSum;
        } else if (node.val == num) {
            node.dup++;
            ans[i] = preSum + node.sum;
        } else if (node.val > num) {
            node.sum++;
            node.left = insert(num, node.left, ans, i, preSum);
        } else {
            node.right = insert(num, node.right, ans, i, preSum + node.dup + node.sum);
        }
        return node;
    }
http://traceformula.blogspot.com/2015/12/count-of-smaller-numbers-after-self.html
https://leetcode.com/discuss/73803/easiest-java-solution
Traverse from nums[len - 1] to nums[0], and build a binary search tree, which stores:
  1. val: value of nums[i]
  2. count: if val == root.val, there will be count number of smaller numbers on the right
But can we really use balanced tree instead of this one? I mean we need keep the structure of the tree in the inserted order. If we convert it into balance tree, we could get wrong answer.
We don't need to keep the inserted order. Just build the tree from back of the array and sum up all passing node's count.
Also https://leetcode.com/discuss/73280/my-simple-ac-java-binary-search-code
public List<Integer> countSmaller(int[] nums) {
    List<Integer> res = new ArrayList<>();
    if(nums == null || nums.length == 0) return res;
    TreeNode root = new TreeNode(nums[nums.length - 1]);
    res.add(0);
    for(int i = nums.length - 2; i >= 0; i--) {
        int count = insertNode(root, nums[i]);
        res.add(count);
    }
    Collections.reverse(res);
    return res;
}
public int insertNode(TreeNode root, int val) {
    int thisCount = 0;
    while(true) {
        if(val <= root.val) {
            root.count++;
            if(root.left == null) {
                root.left = new TreeNode(val); break;
            } else {
                root = root.left;
            }
        } else {
            thisCount += root.count;
            if(root.right == null) {
                root.right = new TreeNode(val); break;
            } else {
                root = root.right;
            }
        }
    }
    return thisCount;
}
class TreeNode {
TreeNode left; 
TreeNode right;
int val;
int count = 1;
public TreeNode(int val) {
    this.val = val;
}
}
Here is the solution but getting TLE . You know why, thats because headset.size() is O(N) surprisngly. SO we cant use this Treeset/Treemap
public List<Integer> countSmaller(int[] nums) {
        if(nums==null || nums.length==0)
            return new ArrayList<Integer>();
        List<Integer> l =new ArrayList<Integer>();

        TreeSet<Integer> s=new TreeSet<>();
        s.add(nums[nums.length-1]);
        l.add(0);
        for( int i=nums.length-2;i>=0;i--){
            SortedSet<Integer> s1=s.headSet(nums[i]);
            l.add(s1.size());
            s.add(nums[i]);

        }
        Collections.reverse(l);
        return l;
}


  1.     class Node {  
  2.         Node left, right;  
  3.         int val, sum, dup = 1;  
  4.         public Node(int v, int s) {  
  5.             val = v;  
  6.             sum = s;  
  7.         }  
  8.     }  
  9.     public List<Integer> countSmaller(int[] nums) {  
  10.         Integer[] ans = new Integer[nums.length];  
  11.         Node root = null;  
  12.         for (int i = nums.length - 1; i >= 0; i--) {  
  13.             root = insert(nums[i], root, ans, i, 0);  
  14.         }  
  15.         return Arrays.asList(ans);  
  16.     }  
  17.     private Node insert(int num, Node node, Integer[] ans, int i, int preSum) {  
  18.         if (node == null) {  
  19.             node = new Node(num, 0);  
  20.             ans[i] = preSum;  
  21.         } else if (node.val == num) {  
  22.             node.dup++;  
  23.             ans[i] = preSum + node.sum;  
  24.         } else if (node.val > num) {  
  25.             node.sum++;  
  26.             node.left = insert(num, node.left, ans, i, preSum);  
  27.         } else {  
  28.             node.right = insert(num, node.right, ans, i, preSum + node.dup + node.sum);  
  29.         }  
  30.         return node;  
  31.     } 

class Node{ int val, leftSum = 0, count = 0; Node left, right; public Node(int val){ this.val = val; } } public List<Integer> countSmaller(int[] nums) { Integer[] count = new Integer[nums.length]; if(nums.length == 0){ return Arrays.asList(count); } Node root = new Node(nums[nums.length - 1]); for(int i = nums.length - 1; i >= 0; i--){ count[i] = insert(root, nums[i]); } return Arrays.asList(count); } private int insert(Node node, int num){ int sum = 0; while(node.val != num){ if(node.val > num){ if(node.left == null) node.left = new Node(num); node.leftSum++; node = node.left; }else{ sum += node.leftSum + node.count; if(node.right == null) node.right = new Node(num); node = node.right; } } node.count++; return sum + node.leftSum; }

 X. Merge Sort
https://blog.csdn.net/beijingbuaaer/article/details/52224538
Variables We Need
1. left[] and right[] , do the merge sort operation, supposed that left[] and right[]are already sorted.
2. rightcount is used to [record how many numbers from right[] .
3. count[left.length]: Because the right[] doesn’t need count to record this.

Variables We Do
1. Increase the rightcount by 1 when u move a number from right[] into the new sorted array.
2. Increase the count[index of number from the left[]] by the present value of rightcount when u move a number from left[index] into the new sorted array.
https://leetcode.com/problems/count-of-smaller-numbers-after-self/discuss/76584/Mergesort-solution
The smaller numbers on the right of a number are exactly those that jump from its right to its left during a stable sort. So I do mergesort with added tracking of those right-to-left jumps.
def countSmaller(self, nums):
    def sort(enum):
        half = len(enum) / 2
        if half:
            left, right = sort(enum[:half]), sort(enum[half:])
            for i in range(len(enum))[::-1]:
                if not right or left and left[-1][1] > right[-1][1]:
                    smaller[left[-1][0]] += len(right)
                    enum[i] = left.pop()
                else:
                    enum[i] = right.pop()
        return enum
    smaller = [0] * len(nums)
    sort(list(enumerate(nums)))
    return smaller
http://www.voidcn.com/blog/smileyk/article/p-5747482.html
归并排序后，虽然数组有序的，但是原始顺序变化了，计算每个元素数量需要找到他们的位置，因此需要记录每个元素的index。
https://discuss.leetcode.com/topic/31554/11ms-java-solution-using-merge-sort-with-explanation
https://discuss.leetcode.com/topic/55751/3-ways-segment-tree-binary-indexed-tree-merge-sort-clean-java-code
The basic idea is to do merge sort to nums[]. To record the result, we need to keep the index of each number in the original array. So instead of sort the number in nums, we sort the indexes of each number. Example: nums = [5,2,6,1], indexes = [0,1,2,3] After sort: indexes = [3,1,0,2]
While doing the merge part, say that we are merging left[] and right[], left[] and right[] are already sorted.
We keep a rightcount to record how many numbers from right[] we have added and keep an array count[] to record the result.
When we move a number from right[] into the new sorted array, we increase rightcount by 1.
When we move a number from left[] into the new sorted array, we increase count[ index of the number ] by rightcount.
indexes is the array @lzyfriday wants to sort.
new_indexes is a temporary subarray that was created for doing the merge. After the merge was done successfully on the temporary subarray new_indexes, he is overwriting elements of indexes array with the appropriate elements from the temporary subarray new_indexes;
int[] count;
public List<Integer> countSmaller(int[] nums) {
    List<Integer> res = new ArrayList<Integer>();     

    count = new int[nums.length];
    int[] indexes = new int[nums.length];
    for(int i = 0; i < nums.length; i++){
     indexes[i] = i;
    }
    mergesort(nums, indexes, 0, nums.length - 1);
    for(int i = 0; i < count.length; i++){
     res.add(count[i]);
    }
    return res;
}
private void mergesort(int[] nums, int[] indexes, int start, int end){
 if(end <= start){
  return;
 }
 int mid = (start + end) / 2;
 mergesort(nums, indexes, start, mid);
 mergesort(nums, indexes, mid + 1, end);
 
 merge(nums, indexes, start, end);
}
private void merge(int[] nums, int[] indexes, int start, int end){
 int mid = (start + end) / 2;
 int left_index = start;
 int right_index = mid+1;
 int rightcount = 0;     
 int[] new_indexes = new int[end - start + 1];

 int sort_index = 0;
 while(left_index <= mid && right_index <= end){
  if(nums[indexes[right_index]] < nums[indexes[left_index]]){
   new_indexes[sort_index] = indexes[right_index];
   rightcount++;
   right_index++;
  }else{
   new_indexes[sort_index] = indexes[left_index];
   count[indexes[left_index]] += rightcount;
   left_index++;
  }
  sort_index++;
 }
 while(left_index <= mid){
  new_indexes[sort_index] = indexes[left_index];
  count[indexes[left_index]] += rightcount;
  left_index++;
  sort_index++;
 }
 while(right_index <= end){
  new_indexes[sort_index++] = indexes[right_index++];
 }
 for(int i = start; i <= end; i++){
  indexes[i] = new_indexes[i - start];
 }
}
https://discuss.leetcode.com/topic/31162/mergesort-solution/12
The smaller numbers on the right of a number are exactly those that jump from its right to its left during a stable sort. So I do mergesort with added tracking of those right-to-left jumps.
    class Pair {
        int index;
        int val;
        public Pair(int index, int val) {
            this.index = index;
            this.val = val;
        }
    }
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        Pair[] arr = new Pair[nums.length];
        Integer[] smaller = new Integer[nums.length];
        Arrays.fill(smaller, 0);
        for (int i = 0; i < nums.length; i++) {
            arr[i] = new Pair(i, nums[i]);
        }
        mergeSort(arr, smaller);
        res.addAll(Arrays.asList(smaller));
        return res;
    }
    private Pair[] mergeSort(Pair[] arr, Integer[] smaller) {
        if (arr.length <= 1) {
            return arr;
        }
        int mid = arr.length / 2;
        Pair[] left = mergeSort(Arrays.copyOfRange(arr, 0, mid), smaller);
        Pair[] right = mergeSort(Arrays.copyOfRange(arr, mid, arr.length), smaller);
        for (int i = 0, j = 0; i < left.length || j < right.length;) {
            if (j == right.length || i < left.length && left[i].val <= right[j].val) {
                arr[i + j] = left[i];
                smaller[left[i].index] += j;
                i++;
            } else {
                arr[i + j] = right[j];
                j++;
            }
        }
        return arr;
    }

class NumberIndex {
 int number;
 int index;

 NumberIndex(int number, int index) {
  this.number = number;
  this.index = index;
 }

 NumberIndex(NumberIndex another) {
  this.number = another.number;
  this.index = another.index;
 }
}

public List<Integer> countSmaller(int[] nums) {
 NumberIndex[] cnums = new NumberIndex[nums.length];
 for (int i = 0; i < nums.length; i++) {
  cnums[i] = new NumberIndex(nums[i], i);
 }
 int[] smaller = new int[nums.length];
 cnums = sort(cnums, smaller);
 List<Integer> res = new ArrayList<>();
 for (int i : smaller) {
  res.add(i);
 }
 return res;
}

private NumberIndex[] sort(NumberIndex[] nums, int[] smaller) {
 int half = nums.length / 2;
 if (half > 0) {
  NumberIndex[] rightPart = new NumberIndex[nums.length - half];
  NumberIndex[] leftPart = new NumberIndex[half];
  for (int i = 0; i < leftPart.length; i++) {
   leftPart[i] = new NumberIndex(nums[i]);
  }
  for (int i = 0; i < rightPart.length; i++) {
   rightPart[i] = new NumberIndex(nums[half + i]);
  }
  NumberIndex[] left = sort(leftPart, smaller), right = sort(
    rightPart, smaller);
  int m = left.length, n = right.length, i = 0, j = 0;
  while (i < m || j < n) {
   if (j == n || i < m && left[i].number <= right[j].number) {
    nums[i + j] = left[i];
    smaller[left[i].index] += j;
    i++;
   } else {
    nums[i + j] = right[j];
    j++;
   }
  }
 }
 return nums;
}

http://algobox.org/count-of-smaller-numbers-after-self/

Like the merge sort with one exception: we count the number of elements smaller when we merge.
public List<Integer> countSmaller(int[] nums) {
    int n = nums.length;
    int[] ans = new int[n];
    Tuple[] arr = new Tuple[n];
    for (int i = 0; i < n; ++i) arr[i] = new Tuple(nums[i], i);
    sort(ans, arr, n);
    List<Integer> list = new ArrayList<>(n);
    for (int x : ans) list.add(x);
    return list;
}
private Tuple[] sort(int[] ans, Tuple[] a, int n) {
    if (n > 1) {
        int i = n / 2, j = n - i;
        Tuple[] left = sort(ans, Arrays.copyOfRange(a, 0, i), i);
        Tuple[] right = sort(ans, Arrays.copyOfRange(a, i, n), j);
        for (int k = n - 1; k >= 0; --k)
            if (j == 0 || (i > 0 && left[i - 1].val > right[j - 1].val)) {
                ans[left[i - 1].idx] += j;
                a[k] = left[--i];
            } else
                a[k] = right[--j];
    }
    return a;
}
class Tuple {
    public int val;
    public int idx;
    public Tuple(int val, int idx) {
        this.val = val;
        this.idx = idx;
    }
}

http://icqgeeks.com/leetcode-315-count-of-smaller-numbers-after-self-hard/
vector<int> countSmaller(vector<int>& nums)
    {
        vector<int> res;
        int len = nums.size();
        if(len == 0) return res;
        res.resize(nums.size(), 0);
        vector<pair<int, int>> items;
        for(int i = 0; i<len; i++)
            items.push_back(make_pair(i, nums[i]));
         
        mergeSort(items, res);
        return res;
    }
     
    void mergeSort(vector<pair<int, int>>& items, vector<int>& smaller)
    {
        if(items.size() <= 1) return;
         
        int mid = items.size()/2;
        vector<pair<int, int>> left(items.begin(), items.begin() + mid);
        vector<pair<int, int>> right(items.begin() + mid, items.end());
         
        mergeSort(left, smaller);
        mergeSort(right, smaller);
        for(int i = 0, j= 0; i<left.size() || j<right.size(); )
        {
            if(j == right.size() || i<left.size()&&left[i].second <= right[j].second)
            {
                items[i + j] =left[i];
                smaller[left[i].first] += j;
                i++;
            }
            else
            {
                items[i + j] =right[j];
                j++;
            }
        }
    }
https://discuss.leetcode.com/topic/31162/mergesort-solution/26
The smaller numbers on the right of a number are exactly those that jump from its right to its left during a stable sort. So I do mergesort with added tracking of those right-to-left jumps.
Use the idea of merge sort. Key algorithm:
ex:
index: 0, 1
left: 2, 5
right: 1, 6
Each time we choose a left to the merged array. We want to know how many numbers from array right are moved before this number.
For example we take 1 from right array and merge sort it first. Then it’s 2 from left array. We find that there are j numbers moved before this left[i], in this case j == 1.
So the array smaller[original index of 2] += j.
Then we take 5 from array left. We also know that j numbers moved before this 5.
smaller[original index of 6] += j.
ex:
index: 0, 1, 2
left: 4, 5, 6
right: 1, 2, 3
when we take 4 for merge sort. We add j (j == 3) because we already take j numbers before take this 4.
  1. During the merge sort, we have to know number and it’s original index. We use a class called Pair to encapsulate them together.
  2. We need to pass the array smaller to merge sort method call because it might be changed during any level of merge sort. And the final smaller number is add up of all the numbers moved before this value.
def countSmaller(self, nums):
    def sort(enum):
        half = len(enum) / 2
        if half:
            left, right = sort(enum[:half]), sort(enum[half:])
            for i in range(len(enum))[::-1]:
                if not right or left and left[-1][1] > right[-1][1]:
                    smaller[left[-1][0]] += len(right)
                    enum[i] = left.pop()
                else:
                    enum[i] = right.pop()
        return enum
    smaller = [0] * len(nums)
    sort(list(enumerate(nums)))
    return smaller

https://leetcode.com/discuss/73256/mergesort-solution
The smaller numbers on the right of a number are exactly those that jump from its right to its left during a stable sort. So I do mergesort with added tracking of those right-to-left jumps.
  1. def countSmaller(self, nums):  
  2.     def sort(enum):  
  3.         half = len(enum) / 2  
  4.         if half:  
  5.             left, right = sort(enum[:half]), sort(enum[half:])  
  6.             for i in range(len(enum))[::-1]:  
  7.                 if not right or left and left[-1][1] > right[-1][1]:  
  8.                     smaller[left[-1][0]] += len(right)  
  9.                     enum[i] = left.pop()  
  10.                 else:  
  11.                     enum[i] = right.pop()  
  12.         return enum  
  13.     smaller = [0] * len(nums)  
  14.     sort(list(enumerate(nums)))  
  15.     return smaller  
Merge sort (Java)
//not easy to understand: what's the indexes[]?
  1. int[] count;  
  2. public List<Integer> countSmaller(int[] nums) {  
  3.     List<Integer> res = new ArrayList<Integer>();       
  4.   
  5.     count = new int[nums.length];  
  6.     int[] indexes = new int[nums.length];  
  7.     for(int i = 0; i < nums.length; i++){  
  8.         indexes[i] = i;  
  9.     }  
  10.     mergesort(nums, indexes, 0, nums.length - 1);  
  11.     for(int i = 0; i < count.length; i++){  
  12.         res.add(count[i]);  
  13.     }  
  14.     return res;  
  15. }  
  16. private void mergesort(int[] nums, int[] indexes, int start, int end){  
  17.     if(end <= start){  
  18.         return;  
  19.     }  
  20.     int mid = (start + end) / 2;  
  21.     mergesort(nums, indexes, start, mid);  
  22.     mergesort(nums, indexes, mid + 1, end);  
  23.   
  24.     merge(nums, indexes, start, end);  
  25. }  
  26. private void merge(int[] nums, int[] indexes, int start, int end){  
  27.     int mid = (start + end) / 2;  
  28.     int left_index = start;  
  29.     int right_index = mid+1;  
  30.     int rightcount = 0;       
  31.     int[] new_indexes = new int[end - start + 1];  
  32.   
  33.     int sort_index = 0;  
  34.     while(left_index <= mid && right_index <= end){  
  35.         if(nums[indexes[right_index]] < nums[indexes[left_index]]){  
  36.             new_indexes[sort_index] = indexes[right_index];  
  37.             rightcount++;  
  38.             right_index++;  
  39.         }else{  
  40.             new_indexes[sort_index] = indexes[left_index];  
  41.             count[indexes[left_index]] += rightcount;  
  42.             left_index++;  
  43.         }  
  44.         sort_index++;  
  45.     }  
  46.     while(left_index <= mid){  
  47.         new_indexes[sort_index] = indexes[left_index];  
  48.         count[indexes[left_index]] += rightcount;  
  49.         left_index++;  
  50.         sort_index++;  
  51.     }  
  52.     while(right_index <= end){  
  53.         new_indexes[sort_index++] = indexes[right_index++];  
  54.     }  
  55.     for(int i = start; i <= end; i++){  
  56.         indexes[i] = new_indexes[i - start];  
  57.     }  
  58. }  
http://www.hrwhisper.me/leetcode-count-of-smaller-numbers-after-self/
简单的说就是求逆序数。
  1. 使用逆序数有经典的解法为合并排序。
struct Node {
int val;
int index;
int cnt;
Node(int val, int index) : val(val), index(index), cnt(0) {}
bool operator <= (const Node &node2)const {
return val <= node2.val;
}
};
class Solution {
public:
void combine(vector<Node> &nums, int Lpos, int Lend, int Rend, vector<Node> &temp) {
int Rpos = Lend + 1;
int Tpos = Lpos;
int n = Rend - Lpos + 1;
int t = Rpos;
while (Lpos <= Lend && Rpos <= Rend) {
if (nums[Lpos] <= nums[Rpos]) {
temp[Tpos] = nums[Lpos];
temp[Tpos].cnt += Rpos - t ;
Tpos++; Lpos++;
}
else {
temp[Tpos++] = nums[Rpos++];
}
}
while (Lpos <= Lend) {
temp[Tpos] = nums[Lpos];
temp[Tpos].cnt += Rpos - t;
Tpos++; Lpos++;
}
while (Rpos <= Rend)
temp[Tpos++] = nums[Rpos++];
for (int i = 0; i< n; i++, Rend--)
nums[Rend] = temp[Rend];
}
void merge_sort(vector<Node> & nums, int L, int R, vector<Node> &temp) {
if (L < R) {
int m = (L + R) >> 1;
merge_sort(nums, L, m, temp);
merge_sort(nums, m + 1, R, temp);
combine(nums, L, m, R, temp);
}
}
vector<int> countSmaller(vector<int>& nums) {
vector<Node> mynums;
vector<Node> temp(nums.size(), Node(0, 0));
for (int i = 0; i < nums.size(); i++)
mynums.push_back(Node(nums[i], i));
vector<int> ans(nums.size(), 0);
merge_sort(mynums, 0, nums.size() - 1, temp);
for (int i = 0; i < nums.size(); i++)
ans[mynums[i].index] = mynums[i].cnt;
return ans;
}
https://leetcode.com/discuss/73233/complicated-segmentree-solution-hope-to-find-a-better-one
Using a Binary Indexed Tree (Fenwick tree) can shorten the code a lot. :P
    private void add(int[] bit, int i, int val) {
        for (; i < bit.length; i += i & -i) bit[i] += val;
    }

    private int query(int[] bit, int i) {
        int ans = 0;
        for (; i > 0; i -= i & -i) ans += bit[i];
        return ans;
    }

    public List<Integer> countSmaller(int[] nums) {
        int[] tmp = nums.clone();
        Arrays.sort(tmp);
        for (int i = 0; i < nums.length; i++) nums[i] = Arrays.binarySearch(tmp, nums[i]) + 1;
        int[] bit = new int[nums.length + 1];
        Integer[] ans = new Integer[nums.length];
        for (int i = nums.length - 1; i >= 0; i--) {
            ans[i] = query(bit, nums[i] - 1);
            add(bit, nums[i], 1);
        }
        return Arrays.asList(ans);
    }
X. BIT 
https://segmentfault.com/a/1190000008407580
binary index tree也可以做，因为是统计有多少smaller的，其实就是求从最小值到nums[i] - 1的sum。tree的index是nums[i]，要做一个映射，把nums[i]的值映射到[1, # of unique numbers in nums]之间。所以先把array给sort一下，用一个map来做映射。
    public List<Integer> countSmaller(int[] nums) {
        /* binary index tree 
         */
        // reflection first, key: nums[i], value: order
        Map<Integer, Integer> map = new HashMap();
        int[] sorted = Arrays.copyOf(nums, nums.length);
        Arrays.sort(sorted);
        // record the order
        int idx = 1;
        for(int i = 0; i < nums.length; i++) {
            if(!map.containsKey(sorted[i])) map.put(sorted[i], idx++);
        }
        // range will be [1, idx]
        BIT t = new BIT(idx);
        LinkedList<Integer> res = new LinkedList();
        for(int i = nums.length - 1; i >= 0; i--) {
            int sum = t.sum(map.get(nums[i]) - 1);
            res.addFirst(t.sum(map.get(nums[i]) - 1));
            t.add(map.get(nums[i]), 1);
        }
        return res;
    }
https://leetcode.com/problems/count-of-smaller-numbers-after-self/discuss/76621/java-5-methods-merge-sort-binary-indexed-tree-binary-search-tree
https://leetcode.com/problems/count-of-smaller-numbers-after-self/discuss/76611/Short-Java-Binary-Index-Tree-BEAT-97.33-With-Detailed-Explanation

可以从每个元素对其后元素的遍历入手，这个遍历实际上可以看成是求和，即小于该元素的计为1，否则计为0，求和。既然是区间求和，就可以尝试使用线段树或树状数组。这里使用实现更简单的树状数组。
首先将给定的nums的拷贝，排序，然后使用一个哈希表来记录每个值对应的下标。建立一个树状数组tree，对nums从后往前遍历，每次对tree的（1，i）求和。求和之后，将这个元素加入tree中，将其值修改为1.

1. 对原数组nums进行离散化处理（排序+去重），将nums从实数范围映射到 [1, len(set(nums))]，记得到的新数组为iNums
2. 从右向左遍历iNums，对树状数组的iNums[i]位置执行+1操作，然后统计(0, iNums[i])的区间和
也可以用线段树

  1. Binary Indexed Tree, iterate from the back of the array, use the rank as BIT index:
    private void update(int[]BIT, int index, int val) {
        index++;
        while (index < BIT.length) {
            BIT[index] += val;
            index += index & (-index);
        }
    }
    private int getSum(int[]BIT, int index) {
        index++;
        int sum = 0;
        while (index > 0) {
            sum += BIT[index];
            index -= index & (-index);
        }
        return sum;
    }
    public List<Integer> countSmaller(int[] nums) {
        LinkedList<Integer> result = new LinkedList<>();
        if (nums.length == 0) return result;
        int[] sorted = nums.clone();
        Arrays.sort(sorted);
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < sorted.length; i++) {
            map.put(sorted[i], i);
        }
        int[] BIT = new int[nums.length+1];
        for (int i = nums.length-1; i >= 0; i--) {
            result.addFirst(getSum(BIT, map.get(nums[i])-1));
            update(BIT, map.get(nums[i]), 1);
        }
        return result;
    }
  1. Binary Indexed Tree, iterate according to sorted order and use original index (from the back) as BIT index:
    private void update(int[]BIT, int index, int val) {
        index++;
        while (index < BIT.length) {
            BIT[index] += val;
            index += index & (-index);
        }
    }
    private int getSum(int[]BIT, int index) {
        index++;
        int sum = 0;
        while (index > 0) {
            sum += BIT[index];
            index -= index & (-index);
        }
        return sum;
    }
    public List<Integer> countSmaller(int[] nums) {
        int[] sorted = nums.clone();
        Arrays.sort(sorted);
        HashMap<Integer, LinkedList<Integer>> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            LinkedList<Integer> l = map.getOrDefault(nums[i], new LinkedList<>());
            l.add(i);
            map.put(nums[i], l);
        }
        int[] BIT = new int[nums.length+1], count = new int[nums.length];
        for (int i = 0; i < sorted.length; i++) {
            if (i > 0 && sorted[i] == sorted[i-1]) continue;
            LinkedList<Integer> list = map.get(sorted[i]);
            for (int j : list) {
                count[j] = getSum(BIT, nums.length-1-j);
            }
            for (int j : list) {
                update(BIT, nums.length-1-j, 1);
            }
        }
        LinkedList<Integer> result = new LinkedList<>();
        for (int c : count) result.add(c);
        return result;
    }
    https://zxi.mytechroad.com/blog/algorithms/array/leetcode-315-count-of-smaller-numbers-after-self/

     Segment tree:
    TODO
    http://www.jiuzhang.com/solutions/count-of-smaller-number/
    http://bookshadow.com/weblog/2015/12/06/leetcode-count-of-smaller-numbers-after-self/
    http://traceformula.blogspot.com/2015/12/count-of-smaller-numbers-after-self.html
    https://leetcode.com/problems/count-of-smaller-numbers-after-self/discuss/76674/3-Ways-(Segment-Tree-Binary-Indexed-Tree-Merge-Sort)-clean-Java-code
    https://www.cnblogs.com/yrbbest/p/5068550.html
        class SegTreeNode {
        int min, max; // range [min, max]
        int count;
        SegTreeNode left, right;
        
        public int mid() {
            return ((max + 1 - min) / 2 + min);
        }
        
        public SegTreeNode(int min, int max) {
            this.min = min;
            this.max = max;
            count = 0;
        }
    }
    
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> list = new LinkedList<Integer>();
        
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int i : nums) {
            min = min > i ? i : min;
            max = max < i ? i : max;
        }
        
        SegTreeNode root = new SegTreeNode(min, max);
        
        for (int i = nums.length - 1; i >= 0; i--) {
            list.add(0, find(nums[i] - 1, root)); // minus 1, in case there will be a equal one
            add(nums[i], root);
        }
        
        return list;
    }
    
    private int find(int x, SegTreeNode root) {
        if (root == null) return 0;
        
        if (x >= root.max) {
            return root.count;
        } else {
            int mid = root.mid(); 
            if (x < mid) {
                return find(x, root.left);
            } else {
                return find(x, root.left) + find(x, root.right);
            }
        }
    }
    
    private void add(int x, SegTreeNode root) {
        if (x < root.min || x > root.max) return;
       
        root.count++;
        if (root.max == root.min) return;
        
        int mid = root.mid();
        if (x < mid) {
            if (root.left == null) {
                root.left = new SegTreeNode(root.min, mid - 1);
            }
            add(x, root.left);
        } else {
            if (root.right == null) {
                root.right = new SegTreeNode(mid, root.max);
            }
            add(x, root.right);
        }
    }
    X. bit trick
    https://discuss.leetcode.com/topic/31924/o-nlogn-divide-and-conquer-java-solution-based-on-bit-by-bit-comparison
    given two integers, how would you determine which one is larger and which is smaller?
    But now imagine you were the computer, how would you actually do the comparison? Remember now all you can see are two series of binary bits representing the two integers. You have no better ways but start from the most significant bit and check bit by bit towards the least significant bit. The first bit will tell you the sign of the two numbers and you know positive numbers (with sign bit value of 0) will be greater than negative numbers (with sign bit value 1). If they have the same sign, then you continue to the next bit with the idea in mind that numbers with bit value 1 will be greater than those with bit value 0. You compare the two series of binary bits in this manner until at some point you can distinguish them or end up with no more bits to check(means the two integers are equal).
    What if we have an array of integers? It doesn't matter. We can proceed in the same way. First check the sign of each integer and partition them into two groups: positive integers and negative ones. Then for each group, we partition the integers further into two groups depending on the next-bit value: those with bit value 1 and those with bit value 0 (to unify sign partition and other bits partitions, we will call the two groups after each partition as highGroup and lowGroup to indicate that all the integers in the highGroup will be greater than those in the lowGroup). And so on until we either have no numbers to partition or no bits to check. (Here we assume the integers have finite length of bits)
    Now let's turn to our problem: for each integer in an array, count the number of integers to its right that are smaller than it. Based on the analysis above, we will have a group of integers as the input (initially the group will be the same as the input array). we then divide the integers into highGroup and lowGroup according to either the sign bit or other-bit values. Since for each integer in the group, we only care about integers to its right, it would be better if we scan the group from right to left. For each integer currently being checked, if it belongs to the highGroup, we know it will be greater than all those in the lowGroup accumulated so far. We proceed in this fashion until either the group is empty or have no more bits to check.
    Notes:
    1. To unify sign bit partition and other-bit partition, we used a variable called highBit to distinguish these two cases.
    2. we store the indices of the elements instead of the elements themselves as it would be easier to set the results.
    3. I used a customized ListNode instead of the Java built-in lists to avoid reallocation of space for each partition. So after each partition, all elements belonging to the lowGroup will be detached from the input group (which is assumed to be highGroup by default) and form the lowGroup while the remaining elements will be the highGroup.
    4. I reversed the order of the elements when adding them to the list due to list performance consideration.
    The time complexity can be analyzed as follows:
    Let T(n) be the total run time and after the partition, we have b*n number in one group and (1-b)n in the other with 0 <= b <= 1. Now the original problem is divided into two smaller subproblems with size given by bn and (1-b)*n. And the solution to the original problem can be obtained by combining the solutions to the two subproblems in O(n) time, then we have:
    T(n) = T(b*n) + T((1-b)*n) + O(n)
    The solution to the characteristic equation b^x + (1-b)^x = 1 is x = 1 so the runtime complexity will be O(nlogn) according to the master theorem (one tricky scenario is b = 0 or b = 1. In this case the runtime is essentially linear provided the total number of bits in each integer is constant). By the way the space complexity is apparently O(n) due to the partition.
    Update: The time complexity analysis above is based on the assumption that the number of partition is logarithmically dependent on the input array size, which is not the case for this problem. The number of partition is constant provided the integer bit size is constant (See @StefanPochmann's answer below).
    Therefore O(nlogn) is a relaxed upper bound while the algorithm can run in linear time.
    The runtime complexity is indeed linear, provided the bit size for an integer is constant. The nlogn runtime is based on the assumption that the number of partitions is logarithmically dependent on the input size, which is not in this case. By the way, nice job to unify the sign bit and other bits.

    class ListNode {
    int val, size;
    ListNode next;
     
    ListNode(int val) {
     this.val = val;
    }
}
    
public List<Integer> countSmaller(int[] nums) {
    Integer[] res = new Integer[nums.length];
    Arrays.fill(res, 0);
        
    ListNode highGroup = new ListNode(-1), itr = highGroup;
    
    for (int i = nums.length - 1; i >= 0; i--) {
        itr.next = new ListNode(i);
        itr = itr.next;
        highGroup.size++;
    }
        
    countSmallerSub(nums, highGroup, 1 << 31, res);
    return Arrays.asList(res);
}
    
private void countSmallerSub(int[] nums, ListNode highGroup, int mask, Integer[] res) {
    if (mask != 0 && highGroup.size > 1) {
     ListNode lowGroup = new ListNode(-1);
     
     int highBit = (mask < 0 ? 0 : mask);
         
     for (ListNode i1 = highGroup, i2 = lowGroup; i1.next != null;) {
         if ((nums[i1.next.val] & mask) == highBit) {
      res[i1.next.val] += lowGroup.size;
      i1 = i1.next;
              
         } else {
      i2.next = i1.next;
      i1.next = i1.next.next;
      i2 = i2.next;
      i2.next = null;
      lowGroup.size++;
      highGroup.size--;
         }
     }
         
     countSmallerSub(nums, highGroup, mask >>> 1, res);
     countSmallerSub(nums, lowGroup, mask >>> 1, res);
    }
}

    one tricky scenario is b = 0 or b = 1. In this case the runtime is essentially linear provided the total number of bits in each integer is constant
    I think it's linear for any b (if bit size is constant), no? During the whole process, each number is handled at most 32 times.
    Nice one. I tried to deal with the first bit differently, here's the nicest I found:
    public List<Integer> countSmaller(int[] nums) {
    List<Integer> res = new ArrayList<>(nums.length);
    List<Integer> index = new ArrayList<>(nums.length);

    for (int i = nums.length - 1; i >= 0; i--) {
        res.add(0);
        index.add(i);
    }

    countSmallerSub(nums, index, 1 << 31, res);

    return res;
}

private void countSmallerSub(int[] nums, List<Integer> index, int mask, List<Integer> res) {
    if (mask != 0 && index.size() > 1) {
        List<Integer> lowGroup = new ArrayList<>(index.size());
        List<Integer> highGroup = new ArrayList<>(index.size());

        int high = mask < 0 ? 0 : mask;
        for (int i = 0; i < index.size(); i++) {
            if ((nums[index.get(i)] & mask) == high) {
                res.set(index.get(i), res.get(index.get(i)) + lowGroup.size());
                highGroup.add(index.get(i));
            } else {
                lowGroup.add(index.get(i));
            }
        }

        countSmallerSub(nums, lowGroup, mask >>> 1, res);
        countSmallerSub(nums, highGroup, mask >>> 1, res);
    }
}
    X. Using Binary Search
    https://discuss.leetcode.com/topic/31173/my-simple-ac-java-binary-search-code
    http://www.cnblogs.com/grandyang/p/5078490.html
    思路是将给定数组从最后一个开始，用二分法插入到一个新的数组，这样新数组就是有序的，那么此时该数字在新数组中的坐标就是原数组中其右边所有较小数字的个数
    Traverse from the back to the beginning of the array, maintain an sorted array of numbers have been visited. Use findIndex() to find the first element in the sorted array which is larger or equal to target number. For example, [5,2,3,6,1], when we reach 2, we have a sorted array[1,3,6], findIndex() returns 1, which is the index where 2 should be inserted and is also the number smaller than 2. Then we insert 2 into the sorted array to form [1,2,3,6].
    Due to the O(n) complexity of ArrayList insertion, the total runtime complexity is not very fast, but anyway it got AC for around 53ms.
    - maybe we can use a wrapper data structure: hashmap+ linkedlist so O(1) to add, O(1) to get

    here the insertion operation of ArrayList is O(n), thus the worse case here would be O(n^2)
    public List<Integer> countSmaller(int[] nums) {
    Integer[] ans = new Integer[nums.length];
    List<Integer> sorted = new ArrayList<Integer>();
    for (int i = nums.length - 1; i >= 0; i--) {
        int index = findIndex(sorted, nums[i]);
        ans[i] = index;
        sorted.add(index, nums[i]);
    }
    return Arrays.asList(ans);
}
private int findIndex(List<Integer> sorted, int target) {
    if (sorted.size() == 0) return 0;
    int start = 0;
    int end = sorted.size() - 1;
    if (sorted.get(end) < target) return end + 1;
    if (sorted.get(start) >= target) return 0;
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        if (sorted.get(mid) < target) {
            start = mid + 1;
        } else {
            end = mid;
        }
    }
    if (sorted.get(start) >= target) return start;
    return end;
}
    Due to the O(n) complexity of ArrayList insertion, the total runtime complexity is not very fast, but anyway it got AC for around 53ms.
    Very nice solution. A small suggestion about the binary search part. If you have (start < end), then start index will be the solution.
    while (start < end) {
    int mid = start + (end - start) / 2;
    if (sorted.get(mid) < target) {
        start = mid + 1;
    } else {
        end = mid;
    }
}
    A java code with some improvement in the process of binary search
    public List<Integer> countSmaller(int[] nums) {
    Integer[] res = new Integer[nums.length];
    List<Integer> sortedlist = new ArrayList<Integer>();
    for(int i = nums.length-1 ; i >= 0 ; i--) {
        int index = findindex(sortedlist , nums[i]);
        res[i] = index;
        sortedlist.add(index , nums[i]);
    }
    return Arrays.asList(res);
}

protected int findindex(List<Integer> sortedlist , int target) {
    if(sortedlist.size() == 0) return 0;
    int start = 0;
    int end = sortedlist.size()-1;
    if(sortedlist.get(start) >= target) return 0;
    if(sortedlist.get(end) < target) return end+1;
    while(start <= end) {
        int mid = start + (end - start) / 2;
        if(sortedlist.get(mid) < target) {
            start = mid + 1;
        }else {
            end = mid - 1;
        }
    }
    return start; // which can make sure we will return the first index of the target(there may be several target in the list)
}
    X. brute force
    http://www.cnblogs.com/yrbbest/p/5068550.html
        public List<Integer> countSmaller(int[] nums) {
        List<Integer> res = new ArrayList<>();
        if(nums == null || nums.length == 0) {
            return res;
        } 
        for(int i = 0; i < nums.length; i++) {
            int count = 0;
            for(int j = i + 1; j < nums.length; j++) {
                if(nums[j] < nums[i]) {
                    count++;
                }
            }
            res.add(count);
        }
        
        return res;
    }


    Maximal Surpasser Count Problem
    http://www.fgdsb.com/2015/01/11/maximal-surpasser-count/
    输入一个数组，返回数组元素的surpasser个数的最大值。
    数组元素a[i] 的surpasser是指元素a[j], j > i， a[j] > a[i]。
    比如[10, 3, 7, 1, 23, 14, 6, 9] 这个数组中10的surpasser是23,14，个数是2。而3的surpasser是7,23,14,6,9，个数为5，并且是最多的一个。所以返回5。
    利用特殊数据结构的话，本题有很多种做法，比如BST，线段树，点树，树状数组。下面给出一种归并排序思路的解法。实际上跟Inverse Pairs基本是完全一样的。这里关心的是顺序而不是逆序。
    大体思路就是在降序归并排序的过程中每次遇到顺序对就记录下来，比如merge的过程中两个元素分别是3和7，3 < 7，所以3的顺序数+1。最后merge sort完毕后，每个顺序数的个数我们都知道，返回最大值即可。
    思路很简单，唯一tricky的地方就是每次遇到顺序的时候，这个顺序数的个数到底加多少。这个需要注意一下。

    用BST的话也很简单，注意每个节点要存surpasser的数量，O(NlogN)建树，然后O(N)遍历一遍找到最大值即可。注意tricky的地方是BST的定义是不允许有重复的，而这题的输入数组是有重复的，要处理一下这个情况。

















    
int max_surpasser(vector<int> nums) {
    

    
vector<int> temp(nums.size());
    

    
int ret = 0;
    

    
unordered_map<int, int> counts;
    

    

    

    
auto merge = [&](int left, int mid, int right) {
    

    
if(left >= right) return;
    

    
int l = mid, r = right, cur = right;
    

    
while (l >= left && r > mid) {
    

    
if(nums[l] < nums[r]) {
    

    
counts[nums[l]] += r - mid;
    

    
ret = max(ret, counts[nums[l]]);
    

    
temp[cur--] = nums[l--];
    

    
} else {
    

    
temp[cur--] = nums[r--];
    

    
}
    

    
}
    

    
while(l >= left) temp[cur--] = nums[l--];
    

    
while(r > mid) temp[cur--] = nums[r--];       
    

    
copy(temp.begin()+left, temp.begin()+right+1, nums.begin()+left);
    

    
};
    

    
function<void(int,int)> sort = [&](int left, int right) {
    

    
if(left >= right) return;
    

    
int mid = left + (right - left) / 2;
    

    
sort(left, mid);
    

    
sort(mid + 1, right);
    

    
merge(left, mid, right);
    

    
};
    

    
sort(0, (int)nums.size() - 1);
    

    
return ret;
    

    
}
    http://www.shadabahmed.com/blog/2013/03/18/puzzle-a-surpassing-problem/

    https://discuss.leetcode.com/topic/31924/o-nlogn-divide-and-conquer-java-solution-based-on-bit-by-bit-comparison
    https://kennyzhuang.gitbooks.io/algorithms-collection/content/count_of_smaller_numbers_after_self.html

    at
    Labels: , , , , , , , , , , , ,

    Labels

    LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

    Popular Posts