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

题目描述

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

考察公司：小米

考察时间：2025.05.26

image-20241107211724343

思路分析

归并排序

参考代码



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51



func reversePairs(nums []int) int {
	if len(nums) <= 1 {
		return 0
	}

	var merge func(nums []int, left, right int) int
	merge = func(nums []int, left, right int) int {
		if left >= right {
			return 0
		}

		mid := left + (right-left)/2

		count := merge(nums, left, mid) + merge(nums, mid+1, right)

		i, j := left, mid+1
		k := 0
		res := make([]int, right-left+1)
		for i <= mid && j <= right {
			if nums[i] <= nums[j] {
				res[k] = nums[i]
				i++
			} else {
				res[k] = nums[j]
				j++
				count += mid - i + 1
			}
			k++
		}

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

		for p := 0; p < len(res); p++ {
			nums[left+p] = res[p]
		}

		return count
	}

	res := merge(nums, 0, len(nums)-1)
	return res
}





1



write your code here

➡️ 点击查看 Java 题解



1



write your code here
本文作者:
本文链接: https://hgnulb.github.io/blog/2025/57449742
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！