[LeetCode] 315. 计算右侧小于当前元素的个数

题目描述：

给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。

题目链接：

. - 力扣（LeetCode）

题目主要思路：

其实跟 “LCR170. 交易逆序对的总数” 那道题差不多，就是多了个数组来记录原始的index，因为counts[i]的值是nums[i]右侧小于nums[i]的元素的数量，建议先理解 “LCR170. 交易逆序对的总数” 这道题的解题思路后再挑战该题。

LCR170. 交易逆序对的总数题目思路及链接：[LeetCode] LCR170. 交易逆序对的总数-CSDN博客

解题代码：

class Solution {
public:
    vector<int> counts; // 返回的数组
    vector<int> index;  // 记录原始下标的数组
    int tmpNums[500010];
    int tmpIndex[500010];
    vector<int> countSmaller(vector<int>& nums) {
        counts.resize(nums.size());
        index.resize(nums.size());
        for (int i = 0; i < nums.size()-1; ++i) {
            index[i] = i;
        }
        mergeSort(nums, 0, nums.size()-1);
        return counts;
    }
    void mergeSort(vector<int>& nums, int left, int right)
    {
        if (left >= right) return;
        int mid = (left + right) >> 1;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid+1, right);
        int cur1 = left, cur2 = mid+1, i = 0;
        while (cur1 <= mid && cur2 <= right) {
            // 排降序
            if (nums[cur1] <= nums[cur2]) {
                tmpNums[i] = nums[cur2];
                tmpIndex[i++] = index[cur2++];  // 记录更换位置后nums[i]原本的index
            }
            else{
                counts[index[cur1]] += right-cur2+1;
                tmpNums[i] = nums[cur1];
                tmpIndex[i++] = index[cur1++];  // 记录更换位置后nums[i]原本的index
            }
        }
        while (cur1 <= mid) {
            tmpNums[i] = nums[cur1];
            tmpIndex[i++] = index[cur1++];  // 记录更换位置后nums[i]原本的index
        }
        while (cur2 <= right) {
            tmpNums[i] = nums[cur2];
            tmpIndex[i++] = index[cur2++];  // 记录更换位置后nums[i]原本的index
        }

        for (int i = left; i <= right; ++i) {
            nums[i] = tmpNums[i-left];
            index[i] = tmpIndex[i-left];  // 将记录更换位置后的原始index写入到index数组中
        }
    }
};