免费购物网站程序,三亚旅游网页设计,东莞房价最新消息,网站排名优化怎样做题目简述 给定一个序列有n个数#xff0c;求n个数中逆序对的个数#xff0c;逆序对的定义#xff1a;i j a[i] a[j]。
输入格式
第一行包含一个整数n。
第二行包含 n 个整数#xff08;所有整数均在1~1e9范围内#xff09;#xff0c;表示整数数…题目简述 给定一个序列有n个数求n个数中逆序对的个数逆序对的定义i j a[i] a[j]。
输入格式
第一行包含一个整数n。
第二行包含 n 个整数所有整数均在1~1e9范围内表示整数数列。
输出格式
输出一个整数表示逆序对的个数。
输入样例
6 2 3 4 5 6 1 输出样例
5
归并排序应用 归并排序是将一个序列分成两个有序的序列归并两个有序序列归并后则该序列有序是基于分治的思想。
根据逆序对的定义我们也可以使用分治的算法来求解逆序对的数量。如图 我们将序列分成两部分我们发现逆序对的数量是三种逆序对数量的和
左边序列的逆序对 右边序列的逆序对 横跨中间的逆序对
利用归并排序我们可以分别求解左边序列的逆序对的数量和右边序列的逆序对的数量。如何求解横跨中间逆序对的数量呢 归并排序中归并的过程 意味着在归并两个序列的过程中我们就可以计算出横跨中间的逆序对的数量。 时间复杂度O(nlogn)空间复杂度O(N)
//下面的代码是在归并排序的基础上做了改进不同在于有返回值递归终止条件归并第二个序列。
int merge_sort(int a[], int l ,int r){//序列只有一个数if (l r) return 0;//递归左边和右边int mid l r 1;int res merge_sort(a, l , mid) merge_sort(a, mid 1, r);//归并的过程int i l , j mid 1, k 0;while (i mid j r){if (a[i] a[j]) t[k] a[i];else{t[k] a[j];res mid - i 1;}}while (i mid) t[k] a[i];while (j r) t[k] a[j];//还原数组for (int i 0 , j l ; j r ; i , j ) a[j] t[i];return res;
}
