315.Count of Smaller Numbers After Self

Tags: Hard Binary Search Sort Binary Indexed Tree Segment Tree

Links: https://leetcode.com/problems/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:

Input: [5,2,6,1]
Output: [2,1,1,0] 
Explanation:
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.

---

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = nums.size();
        vector<int> tmp;
        vector<int> res(n);
        for (int i = n - 1; i >= 0; --i) {
            res[i] = findPos(tmp, nums[i]);
        }

        return res;
    }

    int findPos(vector<int> & tmp, int target)
    {
        int n = tmp.size();
        int left = 0, right = n;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (tmp[mid] < target) left = mid + 1;
            else right = mid;
        }
        tmp.insert(tmp.begin() + left, target);

        return left;
    }
};

逆序对的扩展应用，其实就是找某一个位置的所有逆序对。以往的逆序对只需要输出总数即可，这里需要输出每个位置的逆序对的个数。

解决逆序对的问题可以有：冒泡排序，归并排序，树状数组，线段树，所以Tag才会有那么多。

这里采取一种比较简便的写法，从序列的尾端开始遍历，用一个辅助数组tmp，每次去查找在tmp里第一个能插入的位置，就变成了熟悉的模型，于是手写一个lower_bound。

时间复杂度$O(n \log n)$，空间复杂度$O(n)$