315-计算右侧小于当前元素的个数

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

类似于剑指 Offer 51. 数组中的逆序对

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

示例 1：

输入：nums = [5,2,6,1]
输出：[2,1,1,0] 
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素

method: 归并排序

因为要找到每个元素的位置，所以用index数组记录nums元素的下标，对index数组进行排序，然后用index数组去找对应的nums元素，累加小于当前元素的个数

vector<int> res;
vector<int> countSmaller(vector<int>& nums) {
    int n = nums.size();
    res.resize(n);
    vector<int> tmp(n);
    vector<int> index(n);
    for (int i = 0; i < n; i++) index[i] = i;
    mergeSort(nums, 0, n - 1, index, tmp);
    return res;
}
void mergeSort(vector<int>& nums, int l, int r, vector<int>& index, vector<int>& tmp) {
    if (l == r) return;
    int mid = l + (r - l) / 2;
    mergeSort(nums, l, mid, index, tmp);
    mergeSort(nums, mid + 1, r, index, tmp);
    int cnt = l, i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (nums[index[i]] <= nums[index[j]]) {
            res[index[i]] += (j - mid - 1); // [mid+1,j)都小于i位置的元素，所以累加
            tmp[cnt++] = index[i++];
        } else {
            tmp[cnt++] = index[j++];
        }
    }
    while (i <= mid) {
        res[index[i]] += (r - mid); // [mid+1,r]都小于i位置的元素
        tmp[cnt++] = index[i++];
    }
    while (j <= r) tmp[cnt++] = index[j++];
    for (int k = l; k <= r; k++) {
        index[k] = tmp[k];
    }
}