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

思路：

这道题目虽然还有其它解法，但我觉得最巧妙的还是利用插入排序：我们将nums中数字以逆序的方式插入一个有序数组中。由于它插入的位置就是它的右边比它小的数字的个数，所以直接就可以采用lower_bound就获得其正确的插入位置。最后把结果数组逆序一下返回即可。不过不好的消息是：由于在vector中插入数字会导致里面的元素整体移动，最坏情况下该算法的时间复杂度高达O(n^2)。

我也尝试采用multiset数据结构来模拟插入排序，因为对于这个数据结构而言，lower_bound和insert的时间复杂度都是O(logn)，但是在提交的时候竟然超时了。看来理论时间复杂度和实际运行的时间复杂度还是有差别的。

代码：

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> sorted;
        vector<int> ret;
        if(nums.size() == 0) {
            return ret;
        }
        for(int i = nums.size() - 1; i >= 0; --i) {
            auto it = lower_bound(sorted.begin(), sorted.end(), nums[i]);
            ret.push_back(distance(sorted.begin(), it));
            sorted.insert(it, nums[i]);
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};