0%

leetcode之面试题51-数组中的逆序对

今天给大家带来一道 leetcode 的算法题。为什么这篇文章要写一道算法题?其实主要是想说之前写的排序算法可不只是为了面试用的

这句话也算是一个小提示,那么你能不能与之前写的排序知识联系起来想到解法呢?

暴力

没啥好说的,一上来,两层 for 循环暴力枚举所有数对,逐一判断即可搞定。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* 暴力法
*/
private int reversePairs(int[] nums) {
// 逆序对总数
int ret = 0;
for (int i = 0; i < nums.length - 1; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] > nums[j]) {
ret++;
}
}
}
return ret;
}

结果当然可想而知,毕竟时间复杂度为 O(n^2)。此外空间复杂度为 O(1)。

归并排序

利用归并排序的思路解这道题,你想到了吗?

前面写归并排序的时候写过归并排序的思路,希望你还有印象(没印象的话可以点击文章底部链接去看看哦)。

其实解这道题我们只需要在 merge 操作上做些思考。还记得 merge 操作吧,它是要把两个有序数组合并成一个有序数组。而我们思考的方向,既可以在左边的有序数组上,也可以在右边的有序数组上,所以这个思路可以有两种写法。下面逐一说明。

在左边的有序数组上思考

假定待 merge 数组如下,记逆序对总数为 ret:

(1)8 < 9,不构成逆序对,此时 ret = 0

(2)12 > 9,构成逆序对,且左数组中 12 后边的数都和 9 构成逆序对,此时 ret = 3

(3)12 < 26,不构成逆序对,此时 ret = 3

(4)16 < 26,不构成逆序对,此时 ret = 3

(5)22 < 26,不构成逆序对,此时 ret = 3

(6)左数组遍历完,右数组剩下的元素入辅助数组。因为此时右数组剩下的值比原左数组的所有值都大,不会构成逆序对,所以这一轮 merge 的最终 ret = 3

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
/**
* 采用归并排序自底向上写法,具体可见归并排序文章
* 当然也可以用自顶向下递归的方式来写,都是一样的,这部分其实也不是解题的重点
*/
public int reversePairs(int[] nums) {
// ret 为逆序对总数
int ret = 0, n = nums.length;
if (n < 2) {
return 0;
}
for (int i = 1; i < n; i *= 2) {
for (int j = 0; j < n - i; j += 2 * i) {
int mid = j + i - 1;
if (nums[mid] > nums[j + i]) {
ret += reversePairsHelper(nums, j, mid, Math.min(mid + i, n - 1));
}
}
}
return ret;
}

/**
* “merge”考虑左数组
*/
private int reversePairsHelper(int[] nums, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0, ret = 0;
while (i <= mid && j <= right) {
if (nums[i] <= nums[j]) {
temp[k++] = nums[i++];
} else {
// 重点
ret += mid - i + 1;
temp[k++] = nums[j++];
}
}
while (i <= mid) {
temp[k++] = nums[i++];
}
while (j <= right) {
temp[k++] = nums[j++];
}
System.arraycopy(temp, 0, nums, left, temp.length);
return ret;
}

在右边的有序数组上思考

要比在左数组思考多考虑一点点,不过也比较简单。

假定待 merge 数组如下,记逆序对总数为 ret:

(1)12 > 9,ret 不变,此时 ret = 0

(2)12 < 26,12 和右数组 26 之前的所有数构成逆序对,此时 ret = 1

(3)28 > 26,ret 不变,此时 ret = 1

(4)28 < 55,28 和右数组 55 之前的所有数构成逆序对,此时 ret = 3

(5)50 < 55,50 和右数组 55 之前的所有数构成逆序对,此时 ret = 5

(6)60 > 55,ret 不变,此时 ret = 5

(7)60 < 64,60 和右数组 64 之前的所有数构成逆序对,此时 ret = 8

(8)左数组遍历完,右数组剩下的元素入辅助数组。因为此时右数组剩下的值比原左数组的所有值都大,不会构成逆序对,所以这一轮 merge 的最终 ret = 8

注意,为什么说要比在左数组思考多考虑一点,就在这里。如果最后的情况是右数组遍历完,左数组剩下的元素入辅助数组。那么此时左数组剩下的值比原右数组的所有值都大,那么此时左数组剩下的值都和原右数组的所有值都能构成逆序对,这部分一定要计算在内!

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
/**
* 代码同上
* 采用归并排序自底向上写法,具体可见归并排序文章
* 当然也可以用自顶向下递归的方式来写,都是一样的,这部分其实也不是解题的重点
*/
public int reversePairs(int[] nums) {
// ret 为逆序对总数
int ret = 0, n = nums.length;
if (n < 2) {
return 0;
}
for (int i = 1; i < n; i *= 2) {
for (int j = 0; j < n - i; j += 2 * i) {
int mid = j + i - 1;
if (nums[mid] > nums[j + i]) {
ret += reversePairsHelper(nums, j, mid, Math.min(mid + i, n - 1));
}
}
}
return ret;
}

/**
* “merge”考虑右数组
*/
private int reversePairsHelper(int[] nums, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0, ret = 0;
while (i <= mid && j <= right) {
if (nums[i] <= nums[j]) {
// 重点
ret += j - mid - 1;
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
while (i <= mid) {
// 重点
ret += right - mid;
temp[k++] = nums[i++];
}
while (j <= right) {
temp[k++] = nums[j++];
}
System.arraycopy(temp, 0, nums, left, temp.length);
return ret;
}

提交成功通过。时间复杂度同归并排序 O(n * logn),空间复杂度也同归并排序 O(n)。

离散化树状数组

这个是从官方的解法中看到的,比较骚气,不过要用到一种新的数据结构 - 树状数组。

接下来说一下树状数组解这道题的思路吧,具体的树状数组和代码想放到下一篇再来写。

树状数组是一种可以动态维护数组前缀和的数据结构,它的主要功能是:

  1. 单点更新 update(i, v):把序列 i 位置的数加上一个值 v,在这道题中 v = 1
  2. 区间查询 query(i):查询序列 [1⋯i] 区间的区间和,即 i 位置的前缀和

其中单点更新和区间查询的时间复杂度都是 O(logn),n 为需要维护前缀和的数组的长度。还要注意,树状数组中 0 索引位置是不参与计算的。(具体原因了解树状数组后就能理解)

假定数组 a 为 [5, 5, 2, 3, 6],记逆序对总数为 ret。我们申请一个新数组,遍历 a,在新数组中记录 a 中每个值出现的次数,最终新数组结果如下:

index 0 1 2 3 4 5 6
value 0 0 1 1 0 2 1

可以看到,a[i] 的前缀和可以表示:a 数组中有多少个数比 a[i] 小。那么,如果 a[i] 之前的数在原数组中是出现在 a[i] 后面的,那么 i - 1 的前缀和就代表这些数和 a[i] 构成的逆序对数量。

明白了这一点,那就好做了。我们可以从后往前遍历 a,当遍历到 a[i] 时,把对应的新数组中 i 位置的值自增 1,然后再计算 i - 1 的前缀和,记到 ret 中。当 a 遍历完成后,ret 即为逆序对总数。

为什么可以这么做呢?因为我们在遍历 a 的过程中,把 a 分成了两部分,一部分遍历过(在新数组中),另一部分待遍历(不在新数组中)。那么对于 a[i] 来说,我们求到的 i - 1 位置的前缀和,就是遍历过的元素中比 a[i] 小的元素的总和,而这些元素在 a 中本来就是排在 a[i] 后面的,但它们的值是比 a[i] 小的,所以这就形成了一个逆序对。

离散化树状数组

确实像上面说的那么做是可以的,但是别忘了题目的限制:0 <= 数组长度 <= 50000,额,其实这个限制还好,内存中放得下。如果限制更大一点,内存中放不下怎么办呢?

其实,就算限制更大一点,大到内存中都放不下,但是给定的数组中肯定也是很多位置是 0,它的有效元素的位置是稀疏的。我们可以想办法让有效位置紧凑一点,减少无效位置的出现,减少空间浪费,这时我们就可以用到这个方法 - 离散化。

也就是说,我们只需要关心有效元素在数组中按大小的排名,来决定它们在数组中的位置即可。

恰好,java 里有一种数据结构可以做到去重并排序这一点,什么呢?就是 TreeSet。

离散化树状数组解这道题的思路大致就说完了。其实有个非常重要的点没有说,那就是:单点更新和区间查询的时间复杂度都是 O(logn) 这个是怎么做到的?如果明白了这一点,那么他为什么叫“树状数组”也就明白了。好了,写不少字了,卖个关子吧。


欢迎关注我的其它发布渠道