-
AcWing788.逆序对的数量（Java）
题目描述
给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第 i 个和第 j个元素，如果满足 i<j且 a[i]>a[j]，则其为一个逆序对；否则不是。
输入格式
第一行包含整数 n，表示数列的长度。
第二行包含 n个整数，表示整个数列。
输出格式
输出一个整数，表示逆序对的个数。
数据范围
1≤n≤100000 数列中的元素的取值范围 1∼10^9
输入样例：
6
2 3 4 5 6 1
输出样例：
5
思路讲解
-
首先还是理解下题意吧，通俗点讲，逆序对就是指，一个数组中的两个数，如果前面的数大于后面的那个数，那么这两个数就组成一个逆序对
-
求逆序对的算法是利用了分治的思想,在分治的过程中会将序列分为两部分，此时逆序对可以分为三种情况：两个数都在左边的（设为s1）。两个数都在右边的（s2），一个数在左边一个数在右边的(s3)。现在假设我们在归并排序的时候写的函数merge_sort(int[] q, int left, int right)可以返回l到r区间中逆序对数量。那么s1便是左半边的返回值，s2则是右半边的返回值，而s3却无法如此得到，因为s3不知道跨度是什么。那么核心问题就在于怎么求s3，以及怎么使我们的merge_sort(int[] arr, int l, int r)可以返回l到r区间中逆序对数量。
-
我们应当确定的是，再归并排序中，其下等待归并的所有小数组，结尾有序数组，也就是说，若a数组中的a1大于b数组中的b1，那么a2，a3······都会是大于b1的，那么我们就会很自然的得到res(最终结果)=mid-i+1。
-
而我们是如何得到情况s1和s2的呢？很显然的是，在递归过程中，s1与s2其实是处于s3的状态的，因此很轻易的就可以得到上述结论
-
需要强调的几点是
-
即使我们是求逆序对数量，也应当在排序后进行“扫尾”工作，以确保后续递归的正常进行
-
由于我们求的是逆序对，所以我们应当将方法返回值设为long类型，因为本题数据范围1≤n≤100000，若数组为降序数组，int类型无法满足要求，应设置为long，
-
代码
import java.util.Scanner;
public class Main {
//开辟足够大的数组空间
static int N = 100010;
static int[] q = new int[N], temp = new int[N];
public static void main(String[] args) {
//输入数组大小以及数组的值
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i = 0; i < n; i++) {
q[i] = sc.nextInt();
}
//运行方法并输出结果
System.out.println(merge_sort(q,0,n-1));
}
public static long merge_sort(int []q,int left,int right) {
//进行判断
if (left >= right) return 0;
//进行递归，将数组分为最小单位的值,接着在从最小进行排序，逐渐到整个数组
int mid = left + (right - left) / 2;
//确立返回值
long res = merge_sort(q,left,mid) + merge_sort(q,mid+1,right);
int i = left, j = mid + 1;//建立双指针，i指向前一个数，j指向后一个数
int k = 0;//令temp从0开始，往其中添加元素
//进行归并操作，将数存放至临时数组temp
while (i <= mid && j <= right) {//确认边界
if (q[i] <= q[j])
temp[k++] = q[i++];
else{
temp[k++] = q[j++];
res += mid - i + 1;
}
}
//防止i或j提前用光的情况发生，并保持后续数组排列正确
while (i <= mid) temp[k++] = q[i++];
while (j <= right) temp[k++] = q[j++];
for(i = left, k = 0; i