LeetCode (315) 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 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].

难易度：Hard

思路

这道题是要求数出数组中每个数字后面比它小的数有几个，然后返回一个新的数组存放这些个数。最直接的方法就是一个一个的遍历，这样复杂度要O(n^2)。所以用另外一个思路，利用二分排序，将数组从最后一个插入到一个新的数组中，这样每个数字插入的位置的序号就是后面比它小的元素的个数。

代码

注： 1. vector.insert(vector.begin()+i,a); 在vector第i个元素后插入a 2. 在进行二分排序时，注意边界值的判断和选择