315. Count of Smaller Numbers After Self

Q:

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

A:
*********首先意识到，这就是数组的插入排序啊。  n* log(n)  应该是足够快了
****嗯，就是找到需要插入的位置，再返回这个位置就可以了。********
******可是，反过来想，如果是数组的话，需要每次挪动啊。******？？？？

******sol： 不需要真的插入，只需要记录其后面有多少个就行。然后，记录其前面的。 不对，这样，还是需要记录进去，否则怎么查呢？ *******


Sol 2： 先排序，



Mistakes: