AcWing788.逆序对的数量（Java）（）

　　本篇文章为你整理了AcWing788.逆序对的数量（Java）（）的详细内容，包含有 AcWing788.逆序对的数量（Java），希望能帮助你了解 AcWing788.逆序对的数量（Java）。

　　题目来源：https://www.acwing.com/problem/content/790/

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

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

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

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

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

　　1≤n≤100000 数列中的元素的取值范围 1∼10^9

　　输入样例：

6
2 3 4 5 6 1

　　输出样例：

　　
首先还是理解下题意吧，通俗点讲，逆序对就是指，一个数组中的两个数，如果前面的数大于后面的那个数，那么这两个数就组成一个逆序对

　　
求逆序对的算法是利用了分治的思想,在分治的过程中会将序列分为两部分，此时逆序对可以分为三种情况：两个数都在左边的（设为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 = right; i ++, k ++) q[i] = temp[k];//把原数组未排序的部分覆盖成已排序部分
 return res;
 }
}

 while (i = mid j = right) {//确认边界
 if (q[i] = q[j])
 temp[k++] = q[i++];
 else{
 temp[k++] = q[j++];
 res += mid - i + 1;
 }
 }

　　这里else写的时候忘记{}了，直接导致无论怎样res都会直接加，导致出错

　　以上就是AcWing788.逆序对的数量（Java）（）的详细内容，想要了解更多 AcWing788.逆序对的数量（Java）的内容，请持续关注盛行IT软件开发工作室。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。

相关文章阅读