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

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

示例 1:

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

限制:

0 <= 数组长度 <= 50000

解决方案

归并时统计逆序对。

class Solution {

    private int[] numbers, result;
    private int count;

    public int reversePairs(int[] nums) {
        int size = nums.length;
        if (size == 0) {
            return 0;
        }
        numbers = nums;
        result = new int[size];
        count = 0;
        mergeSort(0, size - 1);
        return count;
    }

    private void mergeSort(int begin, int end) {
        if (begin == end) {
            return ;
        }
        int middle = (begin + end) / 2;
        mergeSort(begin, middle);
        mergeSort(middle + 1, end);
        merge(begin, end);
    }

    private void merge(int begin, int end) {
        int begin1 = begin, end1 = (begin + end) / 2;
        int begin2 = end1 + 1, end2 = end;
        int index = begin;
        while (begin1 <= end1 && begin2 <= end2) {
            if (numbers[begin1] <= numbers[begin2]) {
                result[index++] = numbers[begin1++];
            } else {
                result[index++] = numbers[begin2++];
                count += (end1 - begin1 + 1);
            }
        }
        while (begin1 <= end1) {
            result[index++] = numbers[begin1++];
        }
        while (begin2 <= end2) {
            result[index++] = numbers[begin2++];
        }
        for (int i = begin; i <= end; ++i) {
            numbers[i] = result[i];
        }
    }

}

根据原书示例代码,复制数组的开销可以被优化。

class Solution {

    private int[] arr1, arr2;
    private int count;

    public int reversePairs(int[] nums) {
        int size = nums.length;
        if (size == 0) {
            return 0;
        }
        arr1 = nums.clone();
        arr2 = nums.clone();
        count = 0;
        mergeSort(arr1, arr2, 0, size - 1);
        return count;
    }

    private void mergeSort(int[] arr1, int[] arr2, int begin, int end) {
        if (begin == end) {
            return ;
        }
        int middle = (begin + end) / 2;
        mergeSort(arr2, arr1, begin, middle);
        mergeSort(arr2, arr1, middle + 1, end);
        
        int begin1 = begin, end1 = (begin + end) / 2;
        int begin2 = end1 + 1, end2 = end;
        int index = begin;
        while (begin1 <= end1 && begin2 <= end2) {
            if (arr1[begin1] <= arr1[begin2]) {
                arr2[index++] = arr1[begin1++];
            } else {
                arr2[index++] = arr1[begin2++];
                count += (end1 - begin1 + 1);
            }
        }
        while (begin1 <= end1) {
            arr2[index++] = arr1[begin1++];
        }
        while (begin2 <= end2) {
            arr2[index++] = arr1[begin2++];
        }
    }

}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据