signed

QiShunwang

“诚信为本、客户至上”

【剑指Offer】个人学习笔记_51_数组中的逆序对

2021/5/14 20:10:49   来源:

目录

    • 题目:
        • [剑指 Offer 51. 数组中的逆序对](https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/)
        • 题目分析
    • 初始解答:
    • 学习他人:
      • 方法一:
      • 方法二:
      • 方法三:
    • 总结

刷题日期: 下午7:22 2021年5月14日星期五

个人刷题记录,代码收集,来源皆为leetcode

经过多方讨论和请教,现在打算往Java方向发力

主要答题语言为Java

题目:

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

难度困难411

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

示例 1:

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

限制:

0 <= 数组长度 <= 50000

题目分析

乍一看就是步长为2不断比较数组元素大小然后计数的题目,一定是有什么自己没有想到的难点在里面。

初始解答:

class Solution {
    public int reversePairs(int[] nums) {
        if (nums.length < 2) return 0; //边界条件
        int res = 0;
        for(int i = 0; i < nums.length; i +=2) {
            if(nums[i] > nums[i + 1]) res++;
        }
        return res;
    }
}

输入 [7,5,6,4]

输出 2

差别 预期结果 5

原来不止要求挨着的,只要前面的比后面的大就算。

class Solution {
    public int reversePairs(int[] nums) {
        if (nums.length < 2) return 0; //边界条件
        int res = 0;
        for(int i = 0; i < nums.length; i++) {
            for(int j = i; j < nums.length; j++) {
                if(nums[i] > nums[j]) res++;
            }
        }
        return res;
    }
}

添加备注 最后执行的输入:

[2566,5469,1898,127,2441,4612,2554,5269,2785,5093,3931,2532,1195,1

看来单纯的循环也会被输入太长卡住,而且不是变量不够用。

必须得有什么规律才能解决问题,参考方法二:

class Solution {
    int count = 0;
    public int reversePairs(int[] nums) {
        int len = nums.length;
        if(len < 2) return 0; //边界条件
        mergeSort(nums, 0 , len - 1);
        return count;
    }
    public int[] mergeSort(int[] nums, int l, int r) {
        if (l == r) return new int[]{nums[l]}; //单个序列,返回
        int mid = l + (r - l) / 2;
        int[] left = mergeSort(nums, l, mid);
        int[] right = mergeSort(nums, mid + 1, r);
        int[] res = new int[r - l + 1];
        int i = 0, j = 0, m = 0; //计数器还有用时在外部定义
        while(i < left.length && j < right.length) {
            if(left[i] <= right[j]) res[m++] = left[i++];
            else {
                res[m++] = right[j++];
                count += left.length - i;
            }
        }
        while(i < left.length)
            res[m++] = left[i++];
        while(j < right.length) 
            res[m++] = right[j++];
        return res;
    }
}

执行结果:通过

显示详情 添加备注

执行用时:32 ms, 在所有 Java 提交中击败了98.43%的用户

内存消耗:47.3 MB, 在所有 Java 提交中击败了79.92%的用户

学习他人:

方法一:

JosephimgL3 2021-03-02 练习并归排序

class Solution {
    int ans;
    int[] temp;
    public void mergeSort(int[] nums,int l,int r){
        if(l>=r) return;
        int mid=l+(r-l)/2;
        mergeSort(nums,l,mid);
        mergeSort(nums,mid+1,r);
        merge(nums,l,mid,r);
    }
    public void merge(int[] nums,int l,int mid,int r){
        int i=l,j=mid+1,id=l;
        while(i<=mid&&j<=r){
            if(nums[i]<=nums[j]){
                temp[id++]=nums[i++];
            }
            else{
                ans+=mid-i+1;
                temp[id++]=nums[j++];
            }
        }
        while(i<=mid) temp[id++]=nums[i++];
        while(j<=r) temp[id++]=nums[j++];
        for(int k=l;k<=r;k++) nums[k]=temp[k];
    }
    public int reversePairs(int[] nums) {
        ans=0;
        int n=nums.length;
        temp=new int[n];
        mergeSort(nums,0,n-1);
        return ans;
    }
}

方法二:

G_nightL1 2021-02-16

class Solution {
    //归并排序,在其过程中统计逆序数量,右边每次放上去都要加上:left.length - i
    int count = 0;//统计归并过程中的逆序对数情况
    public int reversePairs(int[] nums) {
        int len = nums.length;
        if(len < 2) return 0;//不构成任何一对
        mergesort(nums, 0, len - 1);
        return count;
    }

    public int[] mergesort(int[] nums, int l, int h){
        if(l == h) return new int[]{nums[l]};//单个数据直接返回
        int mid = l + (h - l) / 2;
        int[] left = mergesort(nums, l, mid);
        int[] right = mergesort(nums, mid + 1, h);
        int[] res = new int[h - l + 1];
        int i = 0, j = 0, m = 0;
        while (i < left.length && j < right.length) {
            if(left[i] <= right[j]){
                res[m++] = left[i++];
            }else{
                res[m++] = right[j++];
                count += left.length - i;
            }
        }
        while (i < left.length)
            res[m++] = left[i++];
        while (j < right.length)
            res[m++] = right[j++];
        return res;
    }
}

方法三:

K神 直观来看,使用暴力统计法即可,即遍历数组的所有数字对并统计逆序对数量。此方法时间复杂度为 O(N^2),观察题目给定的数组长度范围 0≤N≤50000 ,可知此复杂度是不能接受的。

作者:jyd
链接:https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/jian-zhi-offer-51-shu-zu-zhong-de-ni-xu-pvn2h/
来源:力扣(LeetCode)

「归并排序」与「逆序对」是息息相关的。归并排序体现了 “分而治之” 的算法思想,具体为:

分: 不断将数组从中点位置划分开(即二分法),将整个数组的排序问题转化为子数组的排序问题;

治: 划分到子数组长度为 1 时,开始向上合并,不断将 较短排序数组 合并为 较长排序数组,直至合并至原数组时完成排序;

class Solution {
    int[] nums, tmp;
    public int reversePairs(int[] nums) {
        this.nums = nums;
        tmp = new int[nums.length];
        return mergeSort(0, nums.length - 1);
    }
    private int mergeSort(int l, int r) {
        // 终止条件
        if (l >= r) return 0;
        // 递归划分
        int m = (l + r) / 2;
        int res = mergeSort(l, m) + mergeSort(m + 1, r);
        // 合并阶段
        int i = l, j = m + 1;
        for (int k = l; k <= r; k++)
            tmp[k] = nums[k];
        for (int k = l; k <= r; k++) {
            if (i == m + 1)
                nums[k] = tmp[j++];
            else if (j == r + 1 || tmp[i] <= tmp[j])
                nums[k] = tmp[i++];
            else {
                nums[k] = tmp[j++];
                res += m - i + 1; // 统计逆序对
            }
        }
        return res;
    }
}

总结

以上就是本题的内容和学习过程了,暴力不能解的,肯定得用效率更高的,但是没想到是排序,还是基础不过关,具体操作先不深究了,日后用到前再复习。

欢迎讨论,共同进步。