逆序对的数量(递归+归并思想)

今天药忘吃喽~ 2023-02-28 04:09 19阅读 0赞

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

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

输入格式

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

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

输出格式

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

数据范围

1≤n≤1000001≤n≤100000

输入样例：

6
    2 3 4 5 6 1

输出样例：5

解题思路:

第一组: 2 3 4 5

第二组:1 6

归并排序时的两组数据每一组都是已序的,第一组中某个值大于第二组中的某个值,那么第一组这个值后面的所有值都大于这个值

比如第一组中,2<>1为逆序对,那么3<>1,4<>1,5<>1都是逆序对

以此递归解决即可

int merge_sort(int a[], int l, int r) {   
    	if (l >= r) return 0;
    
    	int mid = (l + r) >> 1;  //寻找中间点
    
    	int ta = merge_sort(a, l, mid);
    	int tb = merge_sort(a, mid + 1, r);
    
    	int k = 0;  //暂存数组的标志
    	int i = l, j = mid + 1;  //设置起始地点
    	
    	int tc = 0;  //当前部分
    	//排序部分
    	while (i <= mid && j <= r) 
    		if (a[i] <= a[j]) temp[k++] = a[i++];
    		else {
    			temp[k++] = a[j++];
    			tc += r - i + 1;
    		}
    	while(i <= mid)  temp[k++] = a[i++];
    	while(j <= r) temp[k++] = a[j++];
    
    	for (int i = l, j = 0; i <= r; i++, j++) a[i] = temp[j];
    
    	return ta + tb + tc;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，19人围观）

还没有评论，来说两句吧...

相关阅读

相关一、基础算法2：归并排序模板题+算法模板（归并排序，求逆序对的数量）

文章目录算法模板归并排序算法模板求逆序对的数量模板模板题归并排序原题链接

超、凢脫俗/ 2023年10月08日 20:52/ 0 赞/ 160 阅读

相关 788. 逆序对的数量

给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i<j 且 a\[i\]>a\[j\]，则其

秒速五厘米/ 2023年09月30日 11:14/ 0 赞/ 96 阅读

相关归并排序 AcWing 788. 逆序对的数量

归并排序 AcWing 788. 逆序对的数量原题链接 [AcWing 788. 逆序对的数量][AcWing 788.] 算法标签归并排序思路

小鱼儿/ 2023年09月28日 11:09/ 0 赞/ 244 阅读

相关逆序对的数量(递归+归并思想)

给定一个长度为n的整数数列，请你计算数列中的逆序对的数量。逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i < j 且 a\[i\] > a\[j\]，

今天药忘吃喽~/ 2023年02月28日 04:09/ 0 赞/ 20 阅读

相关数组中的逆序对（归并排序思想）

利用归并排序思想这题没有看懂，转来暂存 ![aHR0cHM6Ly91cGxvYWRmaWxlcy5ub3djb2Rlci5jb20vZmlsZXMvMjAxODA1M

心已赠人/ 2023年01月02日 06:23/ 0 赞/ 297 阅读

相关【日常学习】【归并逆序对】codevs1688 求逆序对题解

题目描述 Description 给定一个序列a1,a2,…,an，如果存在i<j并且ai>aj，那么我们称之为逆序对，求逆序对的数目数据范围：N<=105。Ai<

曾经终败给现在/ 2022年08月09日 12:48/ 0 赞/ 341 阅读

相关利用归并排序求逆序对

在逆序对的问题中，如果采用暴力求解的方法，一般也是有效的，但是O(n2)时间复杂度实在是难以接受的。但是对于逆序对问题，却有一个看似不想关的算法来解决–归并排序。时间复杂度和空

以你之姓@/ 2022年08月04日 15:40/ 0 赞/ 319 阅读

相关采用归并排序思想解决逆序对数问题

//归并排序解逆序对数问题 public class MergeSort { static int count=0; publi

秒速五厘米/ 2022年06月18日 11:20/ 0 赞/ 278 阅读

相关 leetcode 493. Reverse Pairs 逆序对数量 + 归并排序做法

Given an array nums, we call (i, j) an important reverse pair if i < j and nums\[i\] > 2

亦凉/ 2022年06月03日 01:08/ 0 赞/ 285 阅读

相关【牛客】求数组中的逆序对-归并思想

有一组数，对于其中任意两个数组，若前面一个大于后面一个数字，则这两个数字组成一个逆序对。请设计一个高效的算法，计算给定数组中的逆序对个数。给定一个int数组A和它的大小n，

本是古典何须时尚/ 2021年10月03日 01:58/ 0 赞/ 371 阅读