[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数组中}}
};