算法：数组中的逆序对

发表于 更新于 分类于 阅读次数： 本文字数： 1.4k 阅读时长 ≈ 1 分钟

题目描述

题目来源：剑指 Offer 51. 数组中的逆序对 - 力扣（LeetCode） (leetcode-cn.com)

数组中的逆序对是数据结构和算法中的一道经典题目。如果A[i]>A[j]并且i<j，那么这就算是一组逆序对。题目要求给定一个数组，求出数组中逆序对的个数

输入：[7,5,6,4]

输出：5

题解

本题可以使用排序的思想，因为在排序中我们发现的不符合排列顺序的数组对都是一组逆序对，我们只需要计算出在排序的过程中交换的次数即可。本题中可以采用时间复杂度为O(logn)的归并排序。代码如下：

基本思路和归并排序是一样的，如果对归并排序的代码不理解的可以先看一看排序算法。

唯一需要注意的地方就是归并的时候的逆序对计算，当我们发现right小于left的时候，right同时也小于left后面的所有元素，我们增加的个数就是mid-left+1（merge函数）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {

    private static int[] aux; // copy of the origin array

    public int reversePairs(int[] nums) {
        if (nums.length < 2) return 0;
        aux = new int[nums.length];
        return subReversePairs(nums, 0, nums.length - 1);
    }

    private int subReversePairs(int[] nums, int lo, int hi) {
        if (lo >= hi) return 0;
        int mid = lo + (hi - lo) / 2;
        int count = 0;
        count += subReversePairs(nums, lo, mid);
        count += subReversePairs(nums, mid+1, hi);
        // 优化：如果左侧最大小于右侧最小，那么就不需要进行归并了
        if (nums[mid] <= nums[mid+1]) return count;
        count += merge(nums, lo, mid, hi);
        return count;
    }

    private int merge(int[] nums, int lo, int mid, int hi) {
        int count = 0;
        for (int i = lo; i <= hi; i++) aux[i] = nums[i];
        int left = lo, right  = mid+1, index = lo;
        while (left <= mid && right <= hi) {
            if (aux[left] <= aux[right]) nums[index++] = aux[left++];
            else if (aux[left] > aux[right]) {
                nums[index++] = aux[right++];
                count += mid - left + 1;
            }
        }
        while (left <= mid) nums[index++] = aux[left++];
        while (right <= hi) nums[index++] = aux[right++];
        return count;
    }
}