剑指offer面试题36 数组中的逆序对

考察点

归并排序
1

知识点

题目

分析
本题目要求数组中的逆序对，比如数据序列7，5，6，4中类似<7,5>，<6,4>这种就叫逆序对，最简单的办法就是依次比较每个元素和其它序列的大小来确定，但是这样的复杂度太高。既然如此我们能不能把这个大问题分解成小问题然后通过递归的方式求解呢？试想一下如果把数组分成{7,5}，{6,4}好像也没什么能优化的点，但是如果顺序换成{5,7}，{4,6}，这里优化点就出来了，第一个子序列最高值大于第二个子序列最高值那就可以充分说明当前逆序对至少有2对，然后再依次处理第一个子序列前面的元素，发现要比第二个子序列的第一个元素大，那这里可以说明逆序对至少有1对。所以通过这里的分析可以发现，一对排好序的2个子序列可以非常高效的确定逆序对的个数，这个时候我们的思维一定要想到归并排序，因为归并排序本身做的一个事情就是先俩俩拆分，然后俩个子序列依次排序合并成一个有序序列，然后再合并，所以在归并排序的过程中我们就可以得到逆序对的个数了

public class ThirtySix {
	public static void main(String[] args) {
		int[] arr= {7,5,6,4};
		System.out.println(getCount(arr));
	}
	public static int getCount(int[] arr) {
		if (arr == null || arr.length <= 0) {
			return -1;
		}
		int brr[] = new int[arr.length];
		for (int i = 0;i<arr.length;i++) {
			brr[i] = arr[i];
		}
		return getCountCore(arr,brr,0,arr.length - 1);
	}
	public static int getCountCore(int[] arr,int[] brr,int start,int end) {
		if (start == end) {
			brr[start] = brr[start];
			return 0;
		}
		int mid = (end - start) / 2;
		//这里注意归并排序一定是要求子序列是有序的，所以这里arr和brr是交替传递的
		int left = getCountCore(brr,arr,start,start + mid);
		int right = getCountCore(brr,arr,start + mid + 1,end);
		int index = end;
		int i = start + mid;
		int j = end;
		int count = 0;
		while(i >= start && j >= start + mid + 1 ) {
			if (arr[i] > arr[j]) {
				count = count + j -start - mid;
				brr[index--] = arr[i--];
			} else {
				brr[index--] = arr[j--];
			}
		}
		while(i >= start) {
			brr[index--] = arr[i--];
		}
		while(j >= start + mid + 1) {
			brr[index--] = arr[j--];
		}
		return left + right + count;
	}
}
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