🌕🌕 剑指 Offer 51. 数组中的逆序对

难度: 🌕🌕

问题描述

---

解法

class Solution {
    public int reversePairs(int[] nums) {
        // 思路：
        // 归并排序
        int len = nums.length;
        return mySol(nums, 0, len - 1);
    }

    private int mySol(int[] nums, int left, int right) {
        // 递归终止条件
        if(left >= right) {
            return 0;
        }
        int mid = left + ((right - left) >> 1);
        int a = mySol(nums, left, mid);
        int b = mySol(nums, mid + 1, right);
        // 在合并之前，统计 跨左右区间的逆序对数量
        int count = 0;
        int i = left;
        int j = mid + 1;
        while(i <= mid && j <= right) {
            if(nums[i] > nums[j]) {
                // [i, mid] 均 > [j]
                count += mid - i + 1;
                j ++;
            } else {
                i ++;
            }
        }
        // 合并区间
        if(nums[mid] > nums[mid + 1]) {
            merge(nums, left, mid, right);
        }
        return a + b + count;
    }

    private void merge(int[] nums, int left, int mid, int right) {
        int len = right - left + 1;
        int[] res = new int[len];
        int index = 0;
        int i = left;
        int j = mid + 1;

        while(i <= mid && j <= right) {
            if(nums[i] <= nums[j]) {
                res[index] = nums[i];
                i ++;
                index ++;
            } else {
                res[index] = nums[j];
                j ++;
                index ++;
            }
        }
        while(i <= mid) {
            res[index] = nums[i];
            i ++;
            index ++;
        }
        while(j <= right) {
            res[index] = nums[j];
            j ++;
            index ++;
        }
        for(int k = 0; k < len; k ++) {
            nums[k + left] = res[k];
        }
    }
}

---

输出