归并排序题目-逆序对的数量

给定一个长度为 n的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 i个和第 j个元素，如果满足 i<j 且 a[i]>a[j]，则其为一个逆序对；否则不是。

输入格式

第一行包含整数 n，表示数列的长度。

第二行包含 n个整数，表示整个数列。

输出格式

输出一个整数，表示逆序对的个数。

数据范围

1≤n≤100000
数列中的元素的取值范围 [1,109]。

输入样例：

6
2 3 4 5 6 1

输出样例：

5

求逆序对数量其实就是在求在两部分有序的数列中，来相互比较两个数列的大小，若第一个数列中有值大于第二个数列的值，便会产生逆序对；因此可以使用归并排序算法的思想来解决；

首先根据归并算法的特点，通过不断被递归，最终一个数列中只含有一个数字，因此是有序的，接着便会来到倒数第二层递归，此时一个数列中含有两个数字，相当于一个数列分为两个数列，对这两个数列的值进行比较，如果符合逆序对的规则，则res加一，通过不断的递归返回，直到最后一层递归返回（也就是第一次递归调用的地方），此时是两个大数列，数列内部数量为n/2;这两个大数列与之前小的数列合并为较大的数列是一样的，都是在数列内是有序的，但数列与数列之间并不是有序的，所以每次递归返回其实都是在比较数列与数列之间的值的大小。

import java.util.*;
public class P788 {
static int N = 100010;
static int[] arr = new int[N];
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();

for(int i = 0;i < n;i++) {
arr[i] = scan.nextInt();
}
System.out.println(merge_sort(0,n-1));
}
public static long merge_sort(int l,int r) {
if(l>=r) return 0;
int mid = l + r >> 1;
long res = merge_sort(l,mid) + merge_sort(mid +1,r);
int k = 0;
int[] temp = new int[r-l+1];
int i= l,j=mid + 1;
while(i<= mid && j<= r ) {
if(arr[i] <= arr[j]) temp[k++] = arr[i++];
else {
temp[k++] = arr[j++];
res+=mid-i+1;
}
}
while(i<= mid) {
temp[k++] = arr[i++];
}
while(j <= r) {
temp[k++] = arr[j++];
}
for( i = l,k = 0;i <= r;i++,k++) arr[i] = temp[k];

return res;
}

}

这里注意一点，因为题目中的数据范围最大是100000,一般对于数据范围大于10w的题目就要考虑数据溢出、时间复杂度等问题。
那么对于最大100000规模的数据，逆序对最多的数量为多少呢？
当数列是一个倒序的数列时应该是逆序对数量最大的时候，每一个数可以和他后面所有的数形成逆数对，如果有n个数，那么总的逆序对数量为：(n-1)+(n-2)+……+1即n(n−1)/2个，大约n22
个，代入10w的数据范围得最多逆数对个数为：5×109，这个数据大于int的范围。所以这个题用int的话会溢出，我们采用long来存结果。

原文地址：https://blog.csdn.net/qq_62609093/article/details/135839085

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！