交易逆序对的总数

题目链接

交易逆序对的总数

题目描述

注意点

• 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;
    }
}

关键点

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