剑指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/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年4月23日
下一篇 2020年4月24日

相关推荐

  • leetcode22-括号生成

    原题 数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。 示例: 输入:n = 3 输出:[ "((()))", "(()())", "…

    算法 2020年4月9日
    0130
  • leetcode72-编辑距离

    原题 给你两个单词 word1 和 word2 ,请你计算出将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作: 插入一个字符 删除一个字…

    2020年4月6日
    0140
  • leetcode443-压缩字符串

    原题 给定一组字符,使用原地算法将其压缩。 压缩后的长度必须始终小于或等于原数组长度。 数组的每个元素应该是长度为1 的字符(不是 int 整数类型)。 在完成原地修改输入数组后,…

    算法 2020年5月28日
    070
  • leetcode105-从前序与中序遍历序列构造二叉树

    原题 根据一棵树的前序遍历与中序遍历构造二叉树。 注意:你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inord…

    算法 2020年1月13日
    090
  • 剑指offer35-复杂链表的复制

    原题(来源Leetcode) 请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random …

    2020年6月13日
    0110
  • leetcode40-组合总和II

    原题 给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字…

    算法 2020年5月2日
    0730
  • leetcode59-螺旋矩阵II

    原题 给定一个正整数 n,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。 示例: 输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, …

    算法 2020年5月13日
    080
  • 剑指offer03-数组中重复的数字

    原题(来源Leetcode) 找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,…

    算法 2020年3月13日
    0150
  • leetcode409-最长回文串

    原题 给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。 在构造过程中,请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。 注意:假设字符串的长…

    算法 2020年3月19日
    0570
  • leetcode456-132模式

    原题 给定一个整数序列:a1, a2, ..., an,一个132模式的子序列 ai, aj, ak 被定义为:当 i < j < k 时,ai < ak &lt…

    算法 2020年1月30日
    0160

发表回复

登录后才能评论