剑指offer51-数组中的逆序对

原题(来源Leetcode)

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

示例 1:

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

限制:

0 <= 数组长度 <= 50000

解法

思想

暴力:双重循环检查,leetcode中超时

分治思想:使用归并排序的算法,每次给左右两个数组合并的时候,若右边数组中指向的元素小于左边数组指向的元素,则也小于左边数组指向的元素后面的任何一个元素(归并排序合并的时候左右两个数组都是有序的),则此时加上左边数组剩余的元素个数即可。

代码

归并排序大复习,这里提供两种写法:

下面是归并排序较简单的写法,就是每次将数组均分成两个子数组,分到不能再分的时候开始合并相邻的两个子数组。这种写法递归中会创建新数组并拷贝,因此时间成本会略高些。

class Solution {
    int count;//全局变量计数
    public int reversePairs(int[] nums) {
        MergeSort(nums);
        return count;
    }
    public int[] MergeSort(int[] array) {
        if (array.length < 2) return array;
        int mid = array.length / 2;
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        return merge(MergeSort(left), MergeSort(right));
    }
    public int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        for (int index = 0, i = 0, j = 0; index < result.length; index++) {
            if (i == left.length)
                result[index] = right[j++];
            else if (j == right.length)
                result[index] = left[i++];
            else if (left[i] > right[j]){
                count+=left.length-i;//加上左边数组剩余的元素个数
                result[index] = right[j++];
            }
            else result[index] = left[i++];
        }
        return result;
    }
}

下面是一种递归过程中不用创建数组的归并排序写法,只使用两个和原数组相同大小的数组来回交换数据(做对方的缓存),在局部上操作,时间成本会比上面创建数组的方法更低些,但是是一个量级的,在leetcode中能取得更好的成绩:

class Solution {
    public int reversePairs(int[] nums) {
        int[] temp = nums.clone();//创建一个和原数组相同大小的数组
        return MergeSort(nums, temp, 0, nums.length - 1);
    }

    //[start,end]确定一个数组范围,即递归中要排序的范围,返回值为合并过程中的计数
    private int MergeSort(int[] nums, int[] temp, int start, int end) {
        if (start >= end) return 0;
        int mid = (start + end)/2;
        int left = MergeSort(temp, nums, start, mid);
        int right = MergeSort(temp, nums, mid + 1, end);

        int count = merge(nums, temp, start, mid+1, end);
        return left + right + count;
    }

    //[left,right)和[right,end]确定数组的两部分,合并temp数组中的这两部分到nums数组
    private int merge(int[] nums, int[] temp, int left, int right, int end) {
        int index = left;
        int leftSize = right;//因为直接使用left和right作为后面使用的双指针,这里保存right原位置作为left指针能移动到的最远处
        int count = 0;//合并过程中计数

        while (index <= end) {
            if (left==leftSize) nums[index] = temp[right++];
            else if (right==end+1) nums[index] = temp[left++];
            else if (temp[left] > temp[right]) {
                count += (leftSize - left);//加上左边部分剩余的元素个数
                nums[index] = temp[right++];
            } else nums[index] = temp[left++];
            index++;
        }

        return count;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e5%89%91%e6%8c%87offer51-%e6%95%b0%e7%bb%84%e4%b8%ad%e7%9a%84%e9%80%86%e5%ba%8f%e5%af%b9/

发表评论

电子邮件地址不会被公开。