通知
关于网站更多信息请加whimurmur模板/jpress插件QQ群(1061691290)            网站从因情语写改为晴雨            这个网站的模板也从calmlog_ex改为 whimurmur

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

142人浏览 / 0人评论 / | 作者:whisper  | 分类: 剑指offer2  | 标签: 剑指offer2  | 

作者:whisper

链接:https://www.proprogrammar.com/article/884

声明:请尊重原作者的劳动,如需转载请注明出处


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

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

示例 1:

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

限制:

0 <= 数组长度 <= 50000


难度:困难;标签:无;编程语言:JAVA


其它解法

这题当时是直接抄了一份题解,如下

class Solution {
    public int reversePairs(int[] nums) {
        int n = nums.length;
        int[] tmp = new int[n];
        System.arraycopy(nums, 0, tmp, 0, n);
        // 离散化
        Arrays.sort(tmp);
        for (int i = 0; i < n; ++i) {
            nums[i] = Arrays.binarySearch(tmp, nums[i]) + 1;
        }
        // 树状数组统计逆序对
        BIT bit = new BIT(n);
        int ans = 0;
        // 看不懂,先这样吧
        for (int i = n - 1; i >= 0; --i) {
            ans += bit.query(nums[i] - 1);
            bit.update(nums[i]);
        }
        return ans;
    }
}

class BIT {
    private int[] tree;
    private int n;

    public BIT(int n) {
        this.n = n;
        this.tree = new int[n + 1];
    }

    public static int lowbit(int x) {
        return x & (-x);
    }

    public int query(int x) {
        int ret = 0;
        while (x != 0) {
            ret += tree[x];
            x -= lowbit(x);
        }
        return ret;
    }

    public void update(int x) {
        while (x <= n) {
            ++tree[x];
            x += lowbit(x);
        }
    }
}

这个解法很简单粗暴,首先找到每个数排序后应该在的位置,如1,3,2,按大小排序后的位置应该是1,3,2,这里是通过Arrays.sort和Arrays.binarySearch实现的,这里用值大小的位置索引代表数的大小关系,把数聚集化了,这样树状数组就和原数组一样长了(其实是+1长),然后使用树状数组,从后向前找逆序数量并更新当前位置,注意查询时要查询比当前数小的,也就是nums[i]-1(数状数组求逆序数是典型操作,可以找资料看一下数状数组)


亲爱的读者:有时间可以点赞评论一下

点赞(0) 打赏

全部评论

还没有评论!
广告位-帮帮忙点下广告