题目链接
交易逆序对的总数
题目描述
注意点
- 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;
}
}
关键点
- 归并排序的思想
- 怎么通过归并的步骤找到某个元素对逆序对总数的贡献
- 注意边界问题