493. Reverse Pairs [Leetcode] [Based on Merge-Sort] [java]

80 阅读 0 评论 53 点赞

我是靠谱客的博主仁爱寒风，最近开发中收集的这篇文章主要介绍493. Reverse Pairs [Leetcode] [Based on Merge-Sort] [java]，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

查看问题

计算目标对数

while (i <= m) {
    j = m+1;
    while (j <= r && nums[i] > (long)nums[j]*2) j ++;
    count += j-m-1;
    i ++;
}

归并排序

while (i <= m && j <= r) {
    if (nums[i] > nums[j]) temp[k++] = nums[j++];
    else temp[k++] = nums[i++];
}
while (i <= m) temp[k++] = nums[i++];
while (j <= r) temp[k++] = nums[j++];

把排好序的两部分结合，得到一个排好序的序列

计算排好序的序列的对数

int i = l,j = m+1,k = m+1, idx = l;
while (i <= m) {
    //不必每次都从第一个开始
    while (k <= r && nums[i] > (long)nums[k]*2) k ++;
    count += k-m-1;

    while (j <= r && nums[i] > nums[j]) temp[idx++] = nums[j++];
    temp[idx++] = nums[i++];
}
while (j <= r) temp[idx++] = nums[j++];

对于已经排好序的序列，可以进行剪枝。

Solution

class Solution {
    private int[] nums;
    private int[] temp;

    public int reversePairs(int[] nums) {
        if (nums.length == 0) return 0;
        this.nums = nums;
        this.temp = 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 count = mergeSort(l,m) + mergeSort(m+1,r);

        int i = l,j = m+1,k = m+1, idx = l;
        while (i <= m) {
            while (k <= r && nums[i] > (long)nums[k]*2) k ++;
            count += k-m-1;

            while (j <= r && nums[i] > nums[j]) temp[idx++] = nums[j++];
            temp[idx++] = nums[i++];
        }

        while (j <= r) temp[idx++] = nums[j++];

        System.arraycopy(temp, l, nums, l, r-l+1);
        return count;
    }

}

其它问题

Wrong Answer
1. [2147483647,2147483647,2147483647,2147483647,2147483647,2147483647]
  Output: 15
  Expected: 0
  
  考虑int溢出的情况，将int类型转为long
2. [2147483647,2147483647,-2147483647,-2147483647,-2147483647,2147483647]
  Output: 10
  Expected: 9
  
  对于一个负数，如果l==r，那么这个数自己跟自己比较是算作一对的
  要避免这种情况，当l==r时，返回0
Runtime Error