必刷算法100题之计算右侧小于当前元素的个数

 题目链接

315. 计算右侧小于当前元素的个数 - 力扣（LeetCode）

题目解析

计算数组里面所有元素右侧比它小的数的个数, 并且组成一个数组,进行返回

算法原理

归并解法(分治)

当前元素的后面, 有多少个比我小(降序)

我们要找到第一比左边小的元素, 这样就可以找到一堆比左边小的元素: right - cur2+1

nums[cur1]对应的位置,里面的ret[原始下标]+=right-cur2+1

我们算出cur1右边有多少个比它小的时候, 就需要把计算出来的个数放进结果数组ret里面

此时我们就需要找到nums数组中当前元素原始下标,然后把数记上 , 此时我们要解决的就是,怎么找到原始的下标, 因为每次归并, nums数组的元素位置会发生改变.

我们使用一个数组的每一个元素来一一对应记录nums每个元素的原始下标

然后在每一次归并排序,排完后,下标也跟着变(绑定移动)

细节问题, 在创建辅助数组进行合并的时候, 需要创建俩个辅助数组, 一个给nums,一个给index,因为俩个数组是同步改变的

代码编写

class Solution {int[] ret;//保存计算出来的每个元素右侧更小的数量int[] index;//用来保存每个元素对应的原始下标int[] tepRet;//用来保存每一段区间排好序的临时数组int[] tepIndex;//用来保存每次归并后元素下标的变化public void mergeSort(int[] nums, int left, int right) {//递归的终点if (left >= right) {return;}//计算中间下标int mid = (right - left) / 2 + left;//递归左边mergeSort(nums, left, mid);//递归右边mergeSort(nums, mid + 1, right);int cur1 = left;//左区间起始位置int cur2 = mid + 1;//右区间起始位置int i = 0;//归并(降序)while (cur1 <= mid && cur2 <= right) {if (nums[cur1] <= nums[cur2]) {//局部排序数组元素,把大的放前面tepRet[i] = nums[cur2];//更新下标tepIndex[i++] = index[cur2++];} else {//升序就说明找到了一堆ret[index[cur1]] += right - cur2 + 1;tepRet[i] = nums[cur1];tepIndex[i++] = index[cur1++];}}//处理剩余元素while (cur1 <= mid) {tepRet[i] = nums[cur1];tepIndex[i++] = index[cur1++];}while (cur2 <= right) {tepRet[i] = nums[cur2];tepIndex[i++] = index[cur2++];}//还原for (int j = left; j <= right; j++) {nums[j] = tepRet[j - left];index[j] = tepIndex[j - left];}}public List<Integer> countSmaller(int[] nums) {int n = nums.length;ret = new int[n];index = new int[n];tepRet = new int[n];tepIndex = new int[n];//记录下原始的下标for (int i = 0; i < n; i++) {index[i] = i;}//归并来进行处理mergeSort(nums, 0, n - 1);ArrayList<Integer> list = new ArrayList<>();for (int x : ret) {list.add(x);}return list;}
}

注意: 1> 我们在进行递归的时候,不仅要保存当前数组值在排序后的的临时数组, 也要保存下标的临时数组

        2> 多思考为什么此时我们临时数组是直接赋值大小都为n,而不是像之前是一个区间数组