LeetCode.剑指offer.051.数组中的逆序对

题目描述

《剑指offer》面试题51. 数组中的逆序对
https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/

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

示例 1:

输入: [7,5,6,4]
输出: 5

限制： 0 <= 数组长度 <= 50000

---

相似题目

315 计算右侧小于当前元素的个数
https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self/

LeetCode.剑指offer.051.数组中的逆序对

---

解题过程

归并排序过程中统计逆序对

利用归并排序中合并过程中前后两个子数组的有序性，对于左（右）子数组中的每个元素可一次性求出其逆序对个数。
有两种考虑方式：
1、左子数组元素 left[i] 归入结果数组时，计算右子数组中比 left[i] 小的元素个数，也就是右子数组中指针 j 之前的元素个数
2、右子数组元素 right[j] 归入结果数组时，计算左子数组中比 right[j] 大的元素个数，也就是左子数组中指针 i 之后剩余的元素个数
两种方式选择其中一种来实现即可，不能都统计，否则就重复计算了。

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

// 基于归并排序的逆序对统计
private static class SolutionV2020MergeSort {
    int count = 0;
    public int reversePairs(int[] nums) {
        if (null == nums || nums.length < 2) {
            return 0;
        }
        count = 0;
        int[] res = mergeSort(nums, 0, nums.length - 1);
//            System.out.println(Arrays.toString(res));
        return count;
    }

    // 归并排序 nums[start...end]，过程中统计逆序对
    public int[] mergeSort(int[] nums, int start, int end) {
        if (start == end) {
            return new int[] {nums[start]};
        }
        int mid = start + (end - start) / 2;
        int[] leftNums = mergeSort(nums, start, mid);
        int[] rightNums = mergeSort(nums, mid + 1, end);
        int[] res = new int[end - start + 1];
        int i = 0, j = 0, k = 0;
        while (i < leftNums.length && j < rightNums.length) {
            if (leftNums[i] <= rightNums[j]) {
                res[k++] = leftNums[i++];
                // 右子数组中有 j 个比 leftNums[i] 小，也就是产生了 j 个逆序对
                count += j;
            } else {
                res[k++] = rightNums[j++];
            }
        }
        while (i < leftNums.length) {
            res[k++] = leftNums[i++];
            // 左子数组有剩余，则对于左子数组中剩余的每个元素，都有 j 个数比他小，也就是右子数组中全部都比他小
            count += j;
        }
        while (j < rightNums.length) {
            res[k++] = rightNums[j++];
        }
        return res;
    }
}

暴力O(n^2)超时

暴力方法很好写，累加每个元素后面比他大的元素个数即可，不过测试用例很变态，肯定会超时，只能通过 35 / 139 个测试用例
时间复杂度 O(n^2)，空间复杂度 O(1)

// 暴力，O(n^2)，超时，35 / 139 个通过测试用例
private static class SolutionV2020Brutal {
    public int reversePairs(int[] nums) {
        if (null == nums || nums.length == 0) {
            return 0;
        }
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[i]) {
                    count ++;
                }
            }
        }
        return count;
    }
}

---

GitHub代码

algorithms/leetcode/offer/_051_ReversePairInArray.java
https://github.com/masikkk/algorithms/blob/master/leetcode/offer/_051_ReversePairInArray.java

---