题目链接
315. 计算右侧小于当前元素的
个数 - 力扣（LeetCode）
题目解析
计算数组里面所有元素右侧比它小的数的个数, 并且组成一个数组,进行返回
算法原理
归并解法(分治)
当前元素的后面, 有多少个比我小(降序)
我们要找到第一比左边小的元素, 这样就可以找到一堆比左边小的元素: right - cur2+1
nums[cur1]对应的位置,里面的ret[原始下标]+=right-cur2+1
此时我们就需要找到数组原始的下标,然后把数记上
我们使用一个数组的每一个元素来一一对应记录nums每个元素的下标
然后在每一次归并排序,排完后,下标也跟着变
细节问题, 在创建辅助数组进行合并的时候, 需要创建俩个辅助数组, 一个给nums,一个给index,因为俩个数组是同步改变的
代码编写
class Solution {int[] ret;//记录结果int[] index; // 标记 nums 中当前元素的原始下标int[] tmpIndex;// 记录临时数组的值int[] tmpNums;//记录临时下标的值public List<Integer> countSmaller(int[] nums) {int n = nums.length;ret = new int[n];index = new int[n];tmpIndex = new int[n];tmpNums = new int[n];
// 初始化 index 数组for (int i = 0; i < n; i++)index[i] = i;mergeSort(nums, 0, n - 1);List<Integer> l = new ArrayList<Integer>();for (int x : ret)l.add(x);return l;}public void mergeSort(int[] nums, int left, int right) {if (left >= right) return;
// 1. 根据中间元素划分区间int mid = (left + right) / 2;
// [left, mid] [mid + 1, right]
// 2. 处理左右两个区间mergeSort(nums, left, mid);mergeSort(nums, mid + 1, right);
// 3. 处理⼀左⼀右的情况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++];} else {ret[index[cur1]] += right - cur2 + 1; // 重点tmpNums[i] = nums[cur1];tmpIndex[i++] = index[cur1++];}}
// 4. 处理剩余的排序⼯作while (cur1 <= mid) {tmpNums[i] = nums[cur1];tmpIndex[i++] = index[cur1++];}while (cur2 <= right) {tmpNums[i] = nums[cur2];tmpIndex[i++] = index[cur2++];}for (int j = left; j <= right; j++) {nums[j] = tmpNums[j - left];index[j] = tmpIndex[j - left];}}
}