参考资料
练习题 icon lost
交流讨论
笔记
img lost

给定一个数组 nums ,如果i<j 且 nums[i]>2*nums[j]我们就将(i,j)称作一个重要翻转对。

你需要返回给定数组中的重要翻转对的数量。

示例 1:
输入: [1,3,2,3,1]
输出: 2


示例 2:
输入: [2,4,3,5,1]
输出: 3


注意:
给定数组的长度不会超过50000。
输入数组中的所有数字都在32位整数的表示范围内。


通过次数9,591
提交次数32,034

前置知识:归并排序、逆序数、分治

公司:阿里、百度、字节

思路1:在归并排序的过程中,假设对于数组nums[l...r]而言,我们已经分别求出了子数组nums[l...m]nums[m+1...r]的翻转对数目,并已将两个子数组分别排好序,则nums[l...r]中的翻转对数目,就等于两个子数组的翻转对数目之和,加上左右端点分别位于两个子数组的翻转对数目。

我们可以为两个数组分别维护指针i,j。对于任意给定的i而言,我们不断地向右移动j,直到nums[i]\leq 2*nums[j]。此时,意味着以i为左端点的翻转对数量为j-m-1。随后,我们再将 ii 向右移动一个单位,并用相同的方式计算以i为左端点的翻转对数量。不断重复这样的过程,就能够求出所有左右端点分别位于两个子数组的翻转对数目。

代码如下:

class Solution{
      private int cnt;
      public int reversePairs(int[] nums){
        int len=nums.length;
        sort(nums, Arrays.copyOf(nums, len),0,len-1);
        return cnt;
    }
    private void sort(int[] src,int[] dest,int s,int e){
        if (s>=e){
            return;
        }
        int mid=(s+e)>>1;
        sort(dest,src,s,mid);
        sort(dest,src,mid+1,e);
        merge(src,dest,s,mid,e);
    }
    private void merge(int[] src,int[] dest,int s,int mid,int e) {
        int i=s,j=mid+1,k=s;
        while (i<=mid&&j<=e){
            if((long)src[i]>2*((long)src[j])){
                cnt+=mid-i+1;
                j++;
            } 
            else{
                i++;
            }
        }
        i=s;
        j=mid+1;
        while(i<=mid&&j<=e){
            if (src[i]<=src[j]){
                dest[k++]=src[i++];
            } 
            else{
                dest[k++]=src[j++];
            }
        }
        while(i<=mid){
            dest[k++]=src[i++];
        }
        while(j<=e){
            dest[k++]=src[j++];
        }
    }
}

思路2:暴力法

读完这道题你应该就能联想到逆序数才⾏。求解逆序数最简单的做法是使⽤双层循环暴⼒求解。我们仿照求解决逆序数的解法来解这道题(其实唯⼀的区别就是系数从 1 变成了 2),但是复杂度很高。代码如下:

class Solution(object):
    def reversePairs(self, nums):
        n = len(nums)
        cnt = 0
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] > 2 * nums[j]:
                    cnt += 1
        return cnt

 

资料来源 LeetCode 493 翻转对
博客作者 zxw6149
前往答题
我的笔记