`

逆序数/逆序数对

J# 
阅读更多
逆序数是个常遇到的问题,主要有两种解法:
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;
	}
}

第一种方法会超时。
有关于逆序数对再续。
分享到:
评论

相关推荐

    求数组的逆序数

    逆序数(Inversion Count)是指在数组或序列中,如果一个大于其后面的元素,则这样的对称为逆序对。逆序数就是数组中逆序对的数量。这个概念在理解数组的有序性、数据的复杂度分析以及解决特定问题时非常有用。 ...

    汇编 得到字母数/数字数/空格数/删去空格后逆序输出

    汇编作业 应用int 21h的01h,02h,09h,0Ah功能实现输入字符串,得到字母数/数字数/空格数/删去空格后逆序输出

    算法-求排列的逆序数(信息学奥赛一本通-T1237).rar

    《算法-求排列的逆序数(信息学奥赛一本通-T1237)》这个主题涉及到的是计算机科学中的一个重要概念,逆序对或逆序数,它在算法设计和分析中扮演着关键角色,特别是在解决排序和组合优化问题时。逆序数是衡量一个...

    分治法求逆序数

    求逆序数的方法很多。最容易想到的办法是分别对序列中每一个元素求其逆序数,再求所有元素的逆序数总和,易分析得出这样的方法其时间复杂度为O(n2)。而这里采用的分治法求逆序数,其时间复杂度为O(nlogn)。

    逆序数程序

    理解逆序数的概念和计算方法,不仅有助于解决特定的编程问题,还有助于提升对排序和算法效率的理解,这对于任何从事计算机科学或相关领域的专业人士来说都是必不可少的技能。通过深入研究和实践这个“逆序数程序”,...

    mergeSort 求逆序数对matlab代码

    算法导论 课上的 用mergesort求逆序数对的matlab源码,想挣点分,所以就不免费下载了~~~~ 见谅

    归并排序求逆序数

    逆序数是指序列中逆序对的总数。 #### 三、归并排序原理 归并排序是一种分治策略的排序算法,其基本思想是将待排序的数据分成若干个子序列,每个子序列是有序的,然后再把有序的子序列合并成整体有序序列。具体...

    分治法求数组中的逆序数

    有一实数序列a1,a2,....an,若i且ai&gt;aj,则(ai,aj)形成了一个逆序对,请使用分治算法求整个序列中逆序对个数,并分析算法时间复杂度。

    利用线段树求逆序数(JAVA)

    逆序数,也被称为逆序对或倒序对,在计算机科学中是一个重要的概念,尤其是在算法设计和数据结构中。在数组或序列中,如果两个元素a和b满足a &gt; b且它们的位置顺序是a在b之前,那么这对(a, b)被称为逆序对。逆序数...

    逆序输出数字.cpp

    逆序输出数字.cpp逆序输出数字.cpp逆序输出数字.cpp逆序输出数字.cpp逆序输出数字.cpp逆序输出数字.cpp逆序输出数字.cpp逆序输出数字.cpp逆序输出数字.cpp逆序输出数字.cpp逆序输出数字.cpp逆序输出数字.cpp逆序输出...

    算法相关-求数列逆序数

    这个“算法相关-求数列逆序数”的主题涉及到一个经典的计算机科学问题,即如何有效地计算一个数列中的逆序对数量。逆序对是指在已排序的数列中,如果前面的元素大于后面的元素,那么这两个元素就构成一个逆序对。 ...

    逆序数转换转换.cpp

    逆序数

    学习电脑信息用while循环获得逆序数

    学习电脑信息用while循环获得逆序数 在计算机编程中,while循环是一种常用的循环结构,可以用来实现各种复杂的算法。今天,我们将学习如何使用while循环来获得逆序数。 什么是逆序数?逆序数是指将一个数字的各个...

    求逆序数对1

    逆序数对算法解析 在算法设计中,逆序数对是一个常见的问题, 它是指在一个序列中,所有的逆序数对的数量。逆序数对是指序列中两个元素之间的逆序关系,即一个元素的值大于另一个元素的值,但它们的索引却是反的。...

    逆序数字.txt

    逆序数字

    关于逆序输出数字的程序

    本文将深入探讨“关于逆序输出数字的程序”这一主题,旨在解析如何利用C或C++编程语言实现对输入数字的逆序输出功能。 ### 一、逆序输出数字的基本概念 逆序输出数字,即根据用户输入的一个整数,将其数字顺序进行...

    程序设计题型中的逆序数解决

    解决逆序数问题汉诺塔问题最合数亲和书等一系类问题

    nixushu.rar_ nixushu_逆序数

    在标签"_nixushu 逆序数"中,"_nixushu"可能是对逆序数的另一种称呼,而“逆序数”再次强调了主题。 压缩包内的文件“www.pudn.com.txt”可能包含了关于逆序数问题的讨论、解析或者是从pudn.com这个网站上获取的...

    归与分治策略实例编程 统计给定数组中的逆序对个数

    统计给定数组中的逆序对个数。 给n个数a1,a2…an,如果存在存在ai&gt;aj,且i,则称这样的元素对,aj&gt;为一个逆序对 统计这n个数中逆序对的总数 比如说,n=5,a1到a5分别为5,3,1,4,3 则逆序对有 ,3&gt;,,1&gt;,,4&gt;,,3&gt;,,1&gt;,,3&gt;共6...

    利用归并排序实现逆序数计算

    利用归并排序实现关于逆序数的计算,Java程序

Global site tag (gtag.js) - Google Analytics