题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

题解一

第一种方法直接一个暴力双重循环统计逆序对。

时间复杂度为O(n^2)，空间复杂度为O(1)。

public int reversePairs(int[] array) {
    int count = 0;
    for (int i = 0; i < array.length; i++) {
        for (int j = i+1; j < array.length; j++) {
            if (array[i] > array[j])
                count++;
        }
    }
    return count;
}

题解二

第二种方法是用归并排序的思想，但是需要辅助数组。采用分治法，在 divide 过程中先将数组分隔成一个个小的子数组，然后在 merge 排序的同时统计出两个相邻子数组之间逆序对的数量。

实际上就是归并排序，只需要在归并排序的 merge 阶段加上一个统计逆序对的方法就好。

时间复杂度为O(nlogn)，空间复杂度为O(n)。

class Solution {
    int count = 0;
    public int reversePairs(int[] nums) {
        if (nums.length == 0)
            return count;
        int[] res = mergeSort(nums, 0, nums.length-1);
        return count;
    }

    private int[] mergeSort(int[] nums, int start, int end) {
        if (start < end) {
            // divide
            int mid = (start + end) >> 1;
            int[] leftArr = mergeSort(nums, start, mid);
            int[] rightArr = mergeSort(nums, mid+1, end);

            // merge
            return merge(leftArr, rightArr);
        } else {
            return new int[] {nums[start]};
        }
    }

    private int[] merge(int[] arr1, int[] arr2) {
        int[] res = new int[arr1.length + arr2.length];
        int idx = 0, i = 0, j = 0;
        while (i < arr1.length && j < arr2.length) {
            if (arr1[i] <= arr2[j]) {
                res[idx++] = arr1[i++];
            } else {
                res[idx++] = arr2[j++];
            }
        }
        while (i < arr1.length) res[idx++] = arr1[i++];
        while (j < arr2.length) res[idx++] = arr2[j++];

        addReversePairs(arr1, arr2);
        return res;
    }

    private void addReversePairs(int[] arr1, int[] arr2) {
        // 统计数组间的逆序对
        int i = arr1.length-1, j = arr2.length-1;
        while (i >= 0 && j >= 0) {
            if (arr1[i] > arr2[j]) {
                count += (j + 1);
                i--;
            } else j--;
        }
    }
}