逆序数是个常遇到的问题,主要有两种解法:
O(n^2)的方法:
int reverse(int a[],int n){
int count = 0;//逆序数
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
if(a[i] > a[j])
count++;
}
}
return count;
}
O(n*logn)的方法,归并:
const int N = 500000;
int a[N];
int swap_space[N];//归并排序的交换空间
long long total;//逆序数
int total = 0;
void merge(int a[], int begin, int mid,int end){
int i = begin;
int j = mid + 1;
int k = begin;
while(i <= mid && j <= end){
if(a[i] < a[j]){
swap_space[k++] = a[i++];
}else{
swap_space[k++] = a[j++];
total += (mid - i + 1);//total is the reverse count
}
}
while(i <= mid)
swap_space[k++] = a[i++];
while(j <= end)
swap_space[k++] = a[j++];
for(i = begin; i <= end; i++){
a[i] = swap_space[i];
}
}
void mergeSort(int a[], int begin, int end){
if(begin != end){
int mid = (begin + end) / 2;
mergeSort(a,begin, mid);
mergeSort(a,mid+1, end);
merge(a,begin,mid,end);
}
}
学以致用:
poj2299:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2299
#include<iostream>
using namespace std;
const int N = 500000;
int a[N];
int swap_space[N];//归并排序的交换空间
long long total;//逆序数
void merge(int a[], int begin, int mid,int end){
int i = begin;
int j = mid + 1;
int k = begin;
while(i <= mid && j <= end){
if(a[i] < a[j]){
swap_space[k++] = a[i++];
}else{
swap_space[k++] = a[j++];
total += (mid - i + 1);
}
}
while(i <= mid)
swap_space[k++] = a[i++];
while(j <= end)
swap_space[k++] = a[j++];
for(i = begin; i <= end; i++){
a[i] = swap_space[i];
}
}
void mergeSort(int a[], int begin, int end){
if(begin != end){
int mid = (begin + end) / 2;
mergeSort(a,begin, mid);
mergeSort(a,mid+1, end);
merge(a,begin,mid,end);
}
}
int main(){
int n;
int i;
while(cin >> n, n){
total = 0;
for(i = 0; i < n; i++){
cin >> a[i];
}
mergeSort(a, 0 , n-1);
cout << total << endl;
}
}
第一种方法会超时。
有关于逆序数对再续。
分享到:
相关推荐
汇编作业 应用int 21h的01h,02h,09h,0Ah功能实现输入字符串,得到字母数/数字数/空格数/删去空格后逆序输出
求逆序数的方法很多。最容易想到的办法是分别对序列中每一个元素求其逆序数,再求所有元素的逆序数总和,易分析得出这样的方法其时间复杂度为O(n2)。而这里采用的分治法求逆序数,其时间复杂度为O(nlogn)。
算法导论 课上的 用mergesort求逆序数对的matlab源码,想挣点分,所以就不免费下载了~~~~ 见谅
逆序数c++源码,直接运行
CRC校验工具 超级好用 16位32位,16进制都可用 异或输出,表逆序,算法逆序还可输出单片机直接可用的CRC算法。
有一实数序列a1,a2,....an,若i且ai>aj,则(ai,aj)形成了一个逆序对,请使用分治算法求整个序列中逆序对个数,并分析算法时间复杂度。
逆序输出数字.cpp逆序输出数字.cpp逆序输出数字.cpp逆序输出数字.cpp逆序输出数字.cpp逆序输出数字.cpp逆序输出数字.cpp逆序输出数字.cpp逆序输出数字.cpp逆序输出数字.cpp逆序输出数字.cpp逆序输出数字.cpp逆序输出...
逆序数
逆序数字
解决逆序数问题汉诺塔问题最合数亲和书等一系类问题
归并排序求逆序数
统计给定数组中的逆序对个数。 给n个数a1,a2…an,如果存在存在ai>aj,且i,则称这样的元素对,aj>为一个逆序对 统计这n个数中逆序对的总数 比如说,n=5,a1到a5分别为5,3,1,4,3 则逆序对有 ,3>,,1>,,4>,,3>,,1>,,3>共6...
利用归并排序实现关于逆序数的计算,Java程序
对于给定的数组A,计算其逆序对的总数。即: image.png 【输入形式】 输入包含1组测试用例。 一个测试用例占一行,第一个整数表示数组的长度,后面紧跟者数组中的各个整数元素,中间都用一个空格分开。 数组的...
求输入数据后求逆序数问题。常用于本科,研究生的算法作业。里面是工程文件,可以直接使用。
采用归并排序的方法来就算一个序列总的逆序数
关于C++数字逆序问题 适合初学者使用,第一次发资源。
利用归并排序求逆序数,复杂度在O(nlgn)含测试用例
a[j] 则称 i j 为a数组的一个逆序对(inversion) 比如<2 3 8 6 1>有5个逆序对 请考虑一个最坏情况O nlogn 的算法确定n个元素的逆序对数目 注意此题请勿用O n^2 的简单枚举去实现 输入格式 第一行:n ...
输出一个不大于5位的数的位数,将它的每个数位上的数字分别输出,并逆序输出。