每个测试案例包括两行:
第一行包含一个整数n,表示数组中的元素个数。其中1 <= n <= 10^5。
第二行包含n个整数,每个数组均为int类型。
4 7 5 6 4
5
直接的做法是逐个统计,复杂度是N^2,可以利用归并排序的思想,在排序过程中统计逆序对的个数。
时间复杂度依然是 N*Log(N)。 可以从代码中看到,只是比归并排序多了一句代码:cnt += (end-j+1);
由于最终个数可能超过int,这里用long long
//============================================================================ // Name : 求逆序对.cpp // Author : coder // Version : // Copyright : www.acmerblog.com // Description : Hello World in C++, Ansi-style //============================================================================ #include <iostream> #include <stdio.h> using namespace std; typedef long long ll; int n, arr[100010], tmp[100010]; //归并排序,过程中 统计逆序数 ll merge(int start, int mid, int end){ ll cnt = 0; int i = start, j = mid+1, k = start; while( i<=mid && j<= end){ //从大到小排序 if(arr[i] > arr[j]){ cnt += (end-j+1); //右面剩下的都是逆序 tmp[k++] = arr[i++]; }else{ tmp[k++] = arr[j++]; } } while(i<=mid) tmp[k++] = arr[i++]; while(j<=end) tmp[k++] = arr[j++]; for(int i=start; i<=end; i++) arr[i] = tmp[i]; return cnt; } ll inversePairs(int start, int end){ ll cnt = 0; if(start < end){ int mid = (start + end)/2; cnt += inversePairs(start, mid); //左半部分 逆序对数量 cnt += inversePairs(mid+1, end); //右半部分 cnt += merge(start, mid, end); //合并两部分,并计算数量 } return cnt; } int main() { //freopen("in.txt", "r", stdin); while( scanf("%d", &n) != EOF){ for(int i=0; i<n; i++) scanf("%d", &arr[i]); ll ans = inversePairs(0, n-1); printf("%lld\n",ans); } return 0; }
相关推荐
剑指Offer 51.数组中的逆序对(csdn)————程序
# Python实现《剑指offer》 部分代码自己添加了一些测试用例, 或者自己添加了一些功能 1. 初级程序员注重算法和数据结构 2. 事先做好准备,对工作有热情 3. 面试过程放松。不要急于写代码,了解清楚所要解决的问题,...
算法-数组逆序重存放(信息学奥赛一本通-T1105).rar
根据题目描述可知,逆序对指的是数组中前一个数字大于后一个数字的组合形式。因此,对于给定的数组来说,最为暴力的办法就是直接一个个进行比较,从头依次遍历找它后面比他小的元素个数,最后统计最终的结果。但是...
统计数组中的逆序对的个数,基于归并排序的思想,先拆分为单个元素,再合并为两个元素的数组,组内统计后,排序,进行组建统计
[Java算法练习]-数组逆序输出.java
js代码-tmp--数组中的逆序对-改
js代码-tmp-数组中的逆序对(wasted)
js代码-tmp-数组中的逆序对(结果对,超时)
有一实数序列a1,a2,....an,若i且ai>aj,则(ai,aj)形成了一个逆序对,请使用分治算法求整个序列中逆序对个数,并分析算法时间复杂度。
java基础面试题数组中逆序对本资源系百度网盘分享地址
设A[1..n]是包含n个不同数的数组,如果i而且A[i]>A[j],则(i,j)为一个逆序组,给出时间复杂度为nlgn算法,确定n个任意元素排列中逆序组的个数。
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P00000007 输入描述: 题目保证输入的...
逆序数c++源码,直接运行
剑指Offer(Python多种思路实现):数组中的逆序对 面试51题: 题目:数组中的逆序对 题目描述 在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序...
广工《算法和高级数据结构教程》 逆序对(树状数组) c语言实现
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。 示例 1: 输入: [7,5,6,4] 输出: 5 限制: 0 <= 数组长度 <= 50000 首先最...