WordPress建站详细过程,企业网页素材,微信做个小程序多少钱,免费下载app软件官网题目描述#xff1a;
给你一个整数数组 nums #xff0c;按要求返回一个新数组 counts 。数组 counts 有该性质#xff1a; counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
题目链接#xff1a;
. - 力扣#xff08;LeetCode#xff09;
题目主要思路
给你一个整数数组 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:vectorint counts; // 返回的数组vectorint index; // 记录原始下标的数组int tmpNums[500010];int tmpIndex[500010];vectorint countSmaller(vectorint 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(vectorint nums, int left, int right){if (left right) return;int mid (left right) 1;mergeSort(nums, left, mid);mergeSort(nums, mid1, right);int cur1 left, cur2 mid1, 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-cur21;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数组中}}
};
