求解数组中的逆序对并优化时间复杂度

68 阅读 0 评论 45 点赞

我是靠谱客的博主贤惠小天鹅，这篇文章主要介绍求解数组中的逆序对并优化时间复杂度，现在分享给大家，希望可以做个参考。

数组中的逆序对

题目描述

有一组数，对于其中任意两个数组，若前面一个大于后面一个数字，则这两个数字组成一个逆序对。请设计一个高效的算法，计算给定数组中的逆序对个数。

给定一个int数组A和它的大小n，请返回A中的逆序对个数。保证n小于等于5000。
在这里插入图片描述

暴力破解

遍历每一个数，比较这个数和它后面的，出现逆序情况计数器就 + 1。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.*;

public class Main {
	public int count(int[] A,int n) {
		int cnt = 0;
		int len = A.length();
		for (int i = 0; i < len; ++i) {
			for (int j = i + 1; j < len; ++j) {
				if (arr[i] > arr[j]) {
					cnt++;
				}
			}
		}
		return cnt;
	}
}

很明显这种做法假设数组中有 n 个数字，每个数字都要和 O(n) 个数字比较，因此算法的时间复杂度是 O(n^2)。这个显然不够优。

分支思想来优化

以数组 {7，5，6，4} 为例来分析统计逆序对的过程。每次扫描到一个数字的时候。我们不能拿它和后面的每一个数字做比较。否则时间复杂度还是 O(n^2),所以其实可以考虑只比较两个相邻的数字。

逆序对的总数 = 左边数组中的逆序对的数量 + 右边数组中逆序对的数量 + 左右结合成新的顺序数组时出现的逆序对数。
在这里插入图片描述
如上图的过程（c）所示，需要注意的是一旦统计了，比如 {7，5} 是一对，就必须对他们排序，防止在以后的统计中再重复统计。

在（d）中合并两个子数组并统计逆序对的具体过程如下：
在这里插入图片描述
P1 和 P2 分别指向数组最后一个数 (因为在此之前两个长度为 2 的数组已经排好序了，并且统计过逆序对了，所以最后一个数都是两边最大的)。

在 中，P1 大于 P2 ，因此第二个数组中的两个数都比 P1 小，也就是逆序对数 +2，并把 7 复制到辅助数组，向前移动 P1 和辅助数组的 P3。

在中，P1 小于当前的 P2，没有逆序对，把当前的 P2 复制到辅助数组即 P3 的位置，并向前移动 P2 和 P3。

在中，P1 大于当前 P2，存在逆序对，由于当前 P2 是数组中的最后一个数字，也就只可能有一个比 P1 小的，把逆序对 +1，并把 P1 复制到辅助数组，即 P3 的位置，此时 P3 前移，由于 P1 所指的数组已经为空了，所以可以直接按顺序把 P2 所指数组中的值复制到辅助数组。

小结统计两个长度为 2 的子数组之间逆序对的过程

用了两个指针分别指向两个数组的末尾，每次比较这两个对应的数字。如果第一个子数组中的数字大于第二份子数组的数字，则构成逆序对，并且逆序对的数组等于第二个数组中剩余数字的个数；如果第一个数组中的数字小于或等于第二个数组的数字，不构成逆序对。

每一次比较结束的时候，都把较大的数字从后往前复制到辅助数组，确保数字递增排序。复制过后，还要把对应的指针往前移动一位进行下一轮。

详细代码

其实上面的排序过程就是归并排序，可以基于归并排序写出代码

复制代码

import java.util.*;

public class AntiOrder {
	public int count(int[] A,int n) {
		if (A == null || n == 0) {
			return 0;
		}
		return mergeSortRecursion(A,0,n-1);
	}
	
	public static int mergeSortRecursion(int[] arr,int l, int r) {
		if (l == r) {
			return 0;
		}
		int mid = (l + r) / 2;
		// 逆序对总数 = 左边数组中逆序对 + 右边 + 左右结合成新顺序数组逆序对数量
		return mergeSortRecursion(arr,l,mid) + mergeSortRecursion(arr,mid+1,r) + merge(arr,l,mid,r);
	}
	
	public static int merge(int[] arr, int left, int mid, int right) {
		int[] temp = new int[right - left + 1];
		int index = 0;
		int i = left;
		int j = mid + 1;
		int inverseNum = 0; // 新增，用来累加数组逆序对
		while (i <= mid && j <= right) {
			if (arr[i] <= arr[j]) {
				temp[index++] = arr[i++];
			} else {
				// 当前一个数组元素大于后一个数组元素时，累加逆序对
				// s[i] > s[j] 推导出 s[i]...s[mid] > s[j]
				inverseNum += (mid - i + 1);
				temp[index++] = arr[j++];
			}
		}
		while (i <= mid) {
			temp[index++] = arr[i++];
		}
		while (j <= right) {
			temp[index++] = arr[j++];
		}
		for (int k = 0; k < temp.length; k++) {
			arr[left++] = temp[k];
		}
		return inverseNum；
	}
}

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
import java.util.*;

public class AntiOrder {
	public int count(int[] A,int n) {
		if (A == null || n == 0) {
			return 0;
		}
		return mergeSortRecursion(A,0,n-1);
	}
	
	public static int mergeSortRecursion(int[] arr,int l, int r) {
		if (l == r) {
			return 0;
		}
		int mid = (l + r) / 2;
		// 逆序对总数 = 左边数组中逆序对 + 右边 + 左右结合成新顺序数组逆序对数量
		return mergeSortRecursion(arr,l,mid) + mergeSortRecursion(arr,mid+1,r) + merge(arr,l,mid,r);
	}
	
	public static int merge(int[] arr, int left, int mid, int right) {
		int[] temp = new int[right - left + 1];
		int index = 0;
		int i = left;
		int j = mid + 1;
		int inverseNum = 0; // 新增，用来累加数组逆序对
		while (i <= mid && j <= right) {
			if (arr[i] <= arr[j]) {
				temp[index++] = arr[i++];
			} else {
				// 当前一个数组元素大于后一个数组元素时，累加逆序对
				// s[i] > s[j] 推导出 s[i]...s[mid] > s[j]
				inverseNum += (mid - i + 1);
				temp[index++] = arr[j++];
			}
		}
		while (i <= mid) {
			temp[index++] = arr[i++];
		}
		while (j <= right) {
			temp[index++] = arr[j++];
		}
		for (int k = 0; k < temp.length; k++) {
			arr[left++] = temp[k];
		}
		return inverseNum；
	}
}