侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【归并排序, 暴力, 遍历】数组中的逆序对

GabrielxD
2022-04-12 / 0 评论 / 0 点赞 / 34 阅读 / 806 字 / 正在检测是否收录...

题目

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


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

示例 1:

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

限制:

0 <= 数组长度 <= 50000

解题

方法一:暴力遍历

思路

暴力遍历每一个元素,再遍历该元素后面的所有元素,如果该元素比后面的大则逆序对增加。
(超时)

代码

class Solution {
    public int reversePairs(int[] nums) {
        int len = nums.length;
        int ans = 0;
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                if (nums[i] > nums[j]) {
                    ans++;
                }
            }
        }

        return ans;
    }
}

方法二:归并排序

思路

在归并排序的合并过程中。
假设我们有两个已排序的序列等待合并,分别是 L=8,12,16,22,100L={8,12,16,22,100}R={9,26,55,64,91}R = \{ 9, 26, 55, 64, 91 \}。一开始我们用指针 lPtr = 0 指向 LL 的首部,rPtr = 0 指向 RR 的头部。记已经合并好的部分为 MM

L = [8, 12, 16, 22, 100]   R = [9, 26, 55, 64, 91]  M = []
     |                          |
   lPtr                       rPtr

我们发现 lPtr 指向的元素小于 rPtr 指向的元素,于是把 lPtr 指向的元素放入答案,并把 lPtr 后移一位。

L = [8, 12, 16, 22, 100]   R = [9, 26, 55, 64, 91]  M = [8]
        |                       |
      lPtr                     rPtr

这个时候我们把左边的 88 加入了答案,我们发现右边没有数比 88 小,所以 88 对逆序对总数的「贡献」为 00
接着我们继续合并,把 99 加入了答案,此时 lPtr 指向 1212rPtr 指向 2626

L = [8, 12, 16, 22, 100]   R = [9, 26, 55, 64, 91]  M = [8, 9]
        |                          |
       lPtr                       rPtr

此时 lPtrrPtr 小,把 lPtr 对应的数加入答案,并考虑它对逆序对总数的贡献为 rPtr 相对 RR 首位置的偏移 11(即右边只有一个数比 1212 小,所以只有它和 1212 构成逆序对),以此类推。

我们发现用这种「算贡献」的思想在合并的过程中计算逆序对的数量的时候,只在 lPtr 右移的时候计算,是基于这样的事实:当前 lPtr 指向的数字比 rPtr 小,但是比 RR 中 [0 ... rPtr - 1] 的其他数字大,[0 ... rPtr - 1] 的其他数字本应当排在 lPtr 对应数字的左边,但是它排在了右边,所以这里就贡献了 rPtr 个逆序对。

代码

class Solution {
    public int[] helper;
    public int ans;
    
    public int reversePairs(int[] nums) {
        helper = new int[nums.length];
        mergeSort(nums, 0, nums.length - 1);
        return ans;
    }

    public void mergeSort(int[] nums, int start, int end) {
        if (start < end) {
            int mid = start + ((end - start) >> 1);
            mergeSort(nums, start, mid);
            mergeSort(nums, mid + 1, end);
            merge(nums, start, end, mid);
        }
    }

    public void merge(int[] nums, int start, int end, int split) {
        System.arraycopy(nums, start, helper, start, end - start + 1);
        int fstHalfIdx = start, secHalfIdx = split + 1, numsIdx = start;
        while (fstHalfIdx <= split && secHalfIdx <= end) {
            if (helper[fstHalfIdx] <= helper[secHalfIdx]) {
                nums[numsIdx++] = helper[fstHalfIdx++];
            } else {
                nums[numsIdx++] = helper[secHalfIdx++];
                ans += split - fstHalfIdx + 1;
            }
        }

        while(fstHalfIdx <= split) {
            nums[numsIdx++] = helper[fstHalfIdx++];
        }
    }
}
0

评论区