315. Count of Smaller Numbers After Self - YRB - 博客园

315. Count of Smaller Numbers After Self - YRB - 博客园

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].

链接： http://leetcode.com/problems/count-of-smaller-numbers-after-self/

题解：

一开始没有什么想法，后来看tag有segment tree，正好前面也做过于是撸了一棵出来，结果碰到一个超常的数据会超时。又试了一下简单的Brute Force，也会超时。最后还是去Discuss区观摩大神们，发现有好些解法，比如以下

1. 利用Merge Sort count Inversion: https://leetcode.com/discuss/73256/mergesort-solution 
2. Binary Search Tree: https://leetcode.com/discuss/73280/my-simple-ac-java-binary-search-code 
3. Building BST :  https://leetcode.com/discuss/73762/9ms-short-java-bst-solution-get-answer-when-building-bst
4. Segment Tree:  https://leetcode.com/discuss/73233/complicated-segmentree-solution-hope-to-find-a-better-one
5. Fenwich Tree (<- fastest I've seen) :   https://leetcode.com/discuss/74961/7ms-java-solution-using-binary-indexed-tree
6. Bit comparision : https://leetcode.com/discuss/74994/nlogn-divide-and-conquer-java-solution-based-bit-comparison

下面代码是参考yavinci大神的，从右向左遍历数组并且构建BST，当前节点node左侧全部是值小于或者等于当前节点val的节点，当前结点node.count就是他们的和。而每次addNode假如发现逆序，则可以取当前节点的count值返回。 一个小地方是，把结果全部加入到List<Integer>里，最后再reverse这个list，要比每次list.add(0, count)速度要快很多。这个算法worst case  time complexity其实还是O(n²)，要有AVL Tree才能缩短到O(nlogn)。 二刷还是要研究一下merge sort的解法。  比较难的Fenwick Tree解法代码很简单，速度也最快，也留给以后再研究了。

Read full article from 315. Count of Smaller Numbers After Self - YRB - 博客园