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

Categories:

Tags:

题目描述
思路分析
1. 解法一：归并排序计数（推荐）
相似题目

题目描述

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

考察公司：小米

考察时间：2025.05.26

思路分析

解法一：归并排序计数（推荐）

核心思路：

归并排序在合并阶段统计逆序对。

当左半部分元素大于右半部分元素时，左侧剩余元素都构成逆序对。

递归分治并累加计数。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示数组长度。

空间复杂度：O(n)，需要辅助数组。

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

    private long mergeSort(int[] nums, int left, int right, int[] temp) {
        if (left >= right) {
            return 0;
        }

        int mid = left + (right - left) / 2;
        long count = 0;
        count += mergeSort(nums, left, mid, temp);
        count += mergeSort(nums, mid + 1, right, temp);

        if (nums[mid] <= nums[mid + 1]) {
            return count;
        }

        count += merge(nums, left, mid, right, temp);
        return count;
    }

    private long merge(int[] nums, int left, int mid, int right, int[] temp) {
        int i = left;
        int j = mid + 1;
        int k = left;
        long count = 0;

        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                count += mid - i + 1;
                temp[k++] = nums[j++];
            }
        }

        while (i <= mid) {
            temp[k++] = nums[i++];
        }
        while (j <= right) {
            temp[k++] = nums[j++];
        }

        for (int p = left; p <= right; p++) {
            nums[p] = temp[p];
        }

        return count;
    }
}

func reversePairs(nums []int) int {
	temp := make([]int, len(nums))
	return int(mergeSort(nums, 0, len(nums)-1, temp))
}

func mergeSort(nums []int, left int, right int, temp []int) int64 {
	if left >= right {
		return 0
	}

	mid := left + (right-left)/2
	count := mergeSort(nums, left, mid, temp) + mergeSort(nums, mid+1, right, temp)
	if nums[mid] <= nums[mid+1] {
		return count
	}

	count += merge(nums, left, mid, right, temp)
	return count
}

func merge(nums []int, left int, mid int, right int, temp []int) int64 {
	i := left
	j := mid + 1
	k := left
	var count int64 = 0

	for i <= mid && j <= right {
		if nums[i] <= nums[j] {
			temp[k] = nums[i]
			i++
		} else {
			count += int64(mid - i + 1)
			temp[k] = nums[j]
			j++
		}
		k++
	}

	for i <= mid {
		temp[k] = nums[i]
		i++
		k++
	}
	for j <= right {
		temp[k] = nums[j]
		j++
		k++
	}

	for p := left; p <= right; p++ {
		nums[p] = temp[p]
	}

	return count
}

相似题目

题目	难度	考察点
315. 计算右侧小于当前元素的个数	困难	归并排序
327. 区间和的个数	困难	归并排序
493. 翻转对	困难	归并排序
912. 排序数组	中等	归并排序
88. 合并两个有序数组	简单	归并

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/57449742