Hard

题目描述

给定一个整数数组 nums，返回数组中翻转对的数量。

翻转对是一对 (i, j)，其中：

  • 0 <= i < j < nums.length 且
  • nums[i] > 2 * nums[j]

示例 1：

输入：nums = [1,3,2,3,1]
输出：2
解释：翻转对为：
(1, 4) --> nums[1] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) --> nums[3] = 3, nums[4] = 1, 3 > 2 * 1

示例 2：

输入：nums = [2,4,3,5,1]
输出：3
解释：翻转对为：
(1, 4) --> nums[1] = 4, nums[4] = 1, 4 > 2 * 1
(2, 4) --> nums[2] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) --> nums[3] = 5, nums[4] = 1, 5 > 2 * 1

约束：

  • 1 <= nums.length <= 5 * 10^4
  • -2^31 <= nums[i] <= 2^31 - 1

解题思路

这道题有多种解法，包括暴力法、归并排序、树状数组等。推荐使用归并排序的分治思想。

暴力解法：双重循环遍历所有可能的 (i, j) 对，时间复杂度 O(n²)，会超时。

归并排序解法（推荐）： 核心思想是在归并排序的过程中统计翻转对的数量。当我们将数组分为左右两部分并分别排序后，需要统计跨越左右两部分的翻转对。

具体步骤：

  1. 递归地对左半部分和右半部分进行排序并统计内部的翻转对
  2. 统计跨越左右两部分的翻转对：对于左半部分的每个元素，在右半部分中找到满足条件的元素个数
  3. 由于两部分都已排序，可以使用双指针技术在 O(n) 时间内完成统计
  4. 最后合并两个有序数组

关键观察：如果 nums[i] > 2 * nums[j] 且数组已排序，那么对于 i 之后的所有元素，都满足条件。

其他解法：

  • 树状数组或线段树：需要先离散化，然后维护区间和
  • 基于 multiset 的有序集合方法

归并排序方法既直观又高效，是这道题的最优解法。

代码实现

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        return mergeSort(nums, 0, nums.size() - 1);
    }
    
private:
    int mergeSort(vector<int>& nums, int left, int right) {
        if (left >= right) return 0;
        
        int mid = left + (right - left) / 2;
        int count = mergeSort(nums, left, mid) + mergeSort(nums, mid + 1, right);
        
        // 统计跨越左右两部分的翻转对
        int j = mid + 1;
        for (int i = left; i <= mid; i++) {
            while (j <= right && (long long)nums[i] > 2LL * nums[j]) {
                j++;
            }
            count += j - (mid + 1);
        }
        
        // 合并两个有序数组
        merge(nums, left, mid, right);
        return count;
    }
    
    void merge(vector<int>& nums, int left, int mid, int right) {
        vector<int> temp(right - left + 1);
        int i = left, j = mid + 1, k = 0;
        
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }
        
        while (i <= mid) temp[k++] = nums[i++];
        while (j <= right) temp[k++] = nums[j++];
        
        for (i = left, k = 0; i <= right; i++, k++) {
            nums[i] = temp[k];
        }
    }
};

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        def mergeSort(left, right):
            if left >= right:
                return 0
            
            mid = (left + right) // 2
            count = mergeSort(left, mid) + mergeSort(mid + 1, right)
            
            # 统计跨越左右两部分的翻转对
            j = mid + 1
            for i in range(left, mid + 1):
                while j <= right and nums[i] > 2 * nums[j]:
                    j += 1
                count += j - (mid + 1)
            
            # 合并两个有序数组
            temp = []
            i, j = left, mid + 1
            while i <= mid and j <= right:
                if nums[i] <= nums[j]:
                    temp.append(nums[i])
                    i += 1
                else:
                    temp.append(nums[j])
                    j += 1
            
            temp.extend(nums[i:mid + 1])
            temp.extend(nums[j:right + 1])
            nums[left:right + 1] = temp
            
            return count
        
        return mergeSort(0, len(nums) - 1)

public class Solution {
    public int ReversePairs(int[] nums) {
        return MergeSort(nums, 0, nums.Length - 1);
    }
    
    private int MergeSort(int[] nums, int left, int right) {
        if (left >= right) return 0;
        
        int mid = left + (right - left) / 2;
        int count = MergeSort(nums, left, mid) + MergeSort(nums, mid + 1, right);
        
        // 统计跨越左右两部分的翻转对
        int j = mid + 1;
        for (int i = left; i <= mid; i++) {
            while (j <= right && (long)nums[i] > 2L * nums[j]) {
                j++;
            }
            count += j - (mid + 1);
        }
        
        // 合并两个有序数组
        Merge(nums, left, mid, right);
        return count;
    }
    
    private void Merge(int[] nums, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }
        
        while (i <= mid) temp[k++] = nums[i++];
        while (j <= right) temp[k++] = nums[j++];
        
        for (i = left, k = 0; i <= right; i++, k++) {
            nums[i] = temp[k];
        }
    }
}

var reversePairs = function(nums) {
    function mergeSort(left, right) {
        if (left >= right) return 0;
        
        const mid = Math.floor((left + right) / 2);
        let count = mergeSort(left, mid) + mergeSort(mid + 1, right);
        
        // 统计跨越左右两部分的翻转对
        let j = mid + 1;
        for (let i = left; i <= mid; i++) {
            while (j <= right && nums[i] > 2 * nums[j]) {
                j++;
            }
            count += j - (mid + 1);
        }
        
        // 合并两个有序数组
        merge(left, mid, right);
        return count;
    }
    
    function merge(left, mid, right) {
        const temp = [];
        let i = left, j = mid + 1, k = 0;
        
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }
        
        while (i <= mid) temp[k++] = nums[i++];
        while (j <= right) temp[k++] = nums[j++];
        
        for (i = left, k = 0; i <= right; i++, k++) {
            nums[i] = temp[k];
        }
    }
    
    return mergeSort(0, nums.length - 1);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n log n)
空间复杂度O(n)

说明：

  • 时间复杂度：归并排序的时间复杂度为 O(n log n)，每次分治时统计翻转对需要 O(n) 时间
  • 空间复杂度：递归调用栈深度为 O(log n)，合并过程需要 O(n) 的辅助数组空间

相关题目