题目链接

交易逆序对的总数

题目描述

注意点

• 0 <= record.length <= 50000

解答思路

• 本题是归并排序的扩展，可以先进入手撕归并排序了解
• 利用归并排序进行合并时，对于左侧区间当前的首个元素leftNum，不论右侧区间当前的首个元素rightNum是否比leftNum大，只要右区间指针不在初始位置，说明右区间都有元素比leftNum小，leftNum对逆序对是有贡献的，具体贡献多少需要找到右区间所有比其小的元素数量，所以还需要继续移动右区间指针直到右区间首个元素比leftNum大或遍历完右区间为止，贡献值就是右区间指针从初始位置移动的步数

代码

class Solution {int res;public int reversePairs(int[] record) {res = 0;mergeSort(record, 0, record.length - 1);return res;}public int[] mergeSort(int[] record, int left, int right) {if (left > right) {return null;}if (left == right) {return new int[] {record[left]};}int mid = (left + right) / 2;int len = right - left + 1;int[] leftArr = mergeSort(record, left, mid);int[] rightArr = mergeSort(record, mid + 1, right);int[] mergeArr = new int[len];int leftIdx = 0, rightIdx = 0;while (leftIdx < leftArr.length || rightIdx < rightArr.length) {// 左区间已遍历完，右区间数组后续值都比左区间大if (leftIdx >= leftArr.length) {mergeArr[leftIdx + rightIdx] = rightArr[rightIdx++];continue;}// 找到左区间比右区间哪些数更大while (rightIdx < rightArr.length && leftArr[leftIdx] > rightArr[rightIdx]) {mergeArr[leftIdx + rightIdx] = rightArr[rightIdx++];}mergeArr[leftIdx + rightIdx] = leftArr[leftIdx++];res += rightIdx;}return mergeArr;}
}

关键点

• 归并排序的思想
• 怎么通过归并的步骤找到某个元素对逆序对总数的贡献
• 注意边界问题