问题描述:若一个数组为[A1, A2, ..., An],若有i<j且Aj>Ai,那么Ai和Aj就构成一个逆序对。该问题是求出数组中所有逆序对的数目。
算法思想:使用分治法可以在O(nlogn)的时间复杂度下,求出逆序对。其思想为,把一个数组拆分为两个子数组,不妨称为L和R,那么原数组的逆序对数就等于L的逆序对数加上R的逆序对数,再加上一个元素在L中另一个元素在R中构成的逆序对数。可以在分解时独立求出L和R中逆序对数,然后合并时再加上L和R共同构成的逆序对数。
public class reverseOrder {
private static int number = 0;
public static void mergeSort(int[] a, int[] b, int begin, int end) {
if (begin < end) {
int mid = (begin + end) / 2;
mergeSort(a, b, begin, mid);
mergeSort(a, b, mid+1, end);
merge(a, b, begin, mid, end);
copy(a, b, begin, end);
}
}
public static void merge(int[] a, int[] b, int begin, int mid, int end) {
int i = begin;
int k = begin;
int j = mid+1;
while (i <= mid && j <= end) {
if (a[i] <= a[j]) {
b[k++] = a[i++];
}
else {
b[k++] = a[j++];
number += mid - i + 1;
}
}
while (i <= mid)
b[k++] = a[i++];
while (j <= end)
b[k++] = a[j++];
}
public static void copy(int[] a, int[] b, int begin, int end) {
for(int i = begin; i <= end; i++)
a[i] = b[i];
}
public static void main(String[] args) {
int[] a = {5, 1, 2, 3, 4};
int[] b = new int[5];
split(a, b, 0, 4);
System.out.println("The number of reverse pair is: " + number);
}
}
分享到:
相关推荐
NlogN求逆序数对#include<iostream>#include<stdio.h>#include<string.h>#include<algorith
求逆序数的方法很多。最容易想到的办法是分别对序列中每一个元素求其逆序数,再求所有元素的逆序数总和,易分析得出这样的方法其时间复杂度为O(n2)。而这里采用的分治法求逆序数,其时间复杂度为O(nlogn)。
请考虑一个最坏情况O nlogn 的算法确定n个元素的逆序对数目 注意此题请勿用O n^2 的简单枚举去实现 输入格式 第一行:n 表示接下来要输入n个元素 n不超过10000 第二行:n个元素序列 输出格式 逆序对的个数 ...
请采用类似“合并排序算法”的分治思路以O(nlogn)的效率来实现逆序对的统计。 一个n个元素序列的逆序对个数由三部分构成: (1)它的左半部分逆序对的个数,(2)加上右半部分逆序对的个数,(3)再加上左半部分...
请考虑一个最坏情况O(nlogn)的算法确定n个元素的逆序对数目。 注意此题请勿用O(n^2)的简单枚举去实现。 并思考如下问题: (1)怎样的数组含有最多的逆序对?最多的又是多少个呢? (2)插入排序的运行时间和数组中...
北大POJ1804-Brainman【借助Mergesort求逆序数O(nlogn)】
求解逆序对数是算法设计的经典题目,也是难以理解的分治算法,本算法采用分治思想利用递归将程序效率提高到nlogn值得学习算法的人参考
逆序对(归并排序)O(nlogn).cpp
逆序对,时间复杂度nlogn,采用修改后的合并排序算法
求逆序对数: 给一列数a1,a2......an,求它的 逆序对数,即有多少个有序对 (i,j),使得i < j 但 ai > aj 第k小数: 输入n个整数和一个正整数k(1 <= k <= n), 输出这些整数从小到大排序后的第k个 11月13日 & ...
1 图论 3 1.1 术语 3 1.2 独立集、覆盖集、支配集之间关系 3 ...6.3.1 归并排序求逆序 72 7 数值分析 72 7.1 二分法 72 7.2 迭代法(x=f(x)) 73 7.3 牛顿迭代 74 7.4 数值积分 74 7.5 高斯消元 75 8 其它 77
1 图论 3 1.1 术语 3 1.2 独立集、覆盖集、支配集之间关系 3 ...6.3.1 归并排序求逆序 72 7 数值分析 72 7.1 二分法 72 7.2 迭代法(x=f(x)) 73 7.3 牛顿迭代 74 7.4 数值积分 74 7.5 高斯消元 75 8 其它 77
| 归并排序求逆序数 25 | 逆序数推排列数 25 | 二分查找 25 | 二分查找(大于等于 V 的第一个值) 25 | 所有数位相加 25 Number 数论 26 1 |递推求欧拉函数 PHI(I) 26 |单独求欧拉函数 PHI(X) 26 | GCD ...
归并排序求逆序数 Pell方程 Catalan数,100以内 欧拉函数讲解 组合计数 组合数计算(double) 组合数计算(高精度) r-组合生成算法 r-排列生成算法 r-错位排列生成算法 图论 传递闭包 欧拉回路判定 有向图...
O(nlogn) C. O(n3) D. O(n2) 【南京理工大学 1998一、1(2分)】 13.以下哪个数据结构不是多型数据类型(D )【中山大学 1999 一、3(1分)】 A.栈 B.广义表 C.有向图 D.字符串 14.以下数据结构中,(A )是...