其实就是二路归并排序,排序的同时记录交换次数就行了。
public class ReversalCount {
private int[] array = null;
private int[] tempArray = null;
public ReversalCount(int[] array) {
this.array = array;
tempArray = new int[array.length];
}
public int calc() {
return calc(0, array.length - 1);
}
private int calc(int l, int r) {
if (l >= r) { // less than two numbers
return 0;
} else if (l + 1 == r) { // two numbers
return (array[l] <= array[r]) ? 0 : swap(l, r);
} else { // three or more numbers
int m = (l + r) / 2;
return calc(l, m) + calc(m + 1, r) + combine(l, m, r);
}
}
private int combine(int l, int m, int r) {
for (int idx = l; idx <= r; idx++) {
tempArray[idx] = array[idx];
}
int count = 0, idx = l, lidx, ridx;
for (lidx = l, ridx = m + 1; lidx <= m && ridx <= r; ) {
if (tempArray[lidx] > tempArray[ridx]) {
array[idx++] = tempArray[ridx++];
count += m - lidx + 1;
} else {
array[idx++] = tempArray[lidx++];
}
}
for (; ridx <= r; ++ridx) {
array[idx++] = tempArray[ridx];
}
for (; lidx <= m; ++lidx) {
array[idx++] = tempArray[lidx];
}
return count;
}
private int swap(int i, int j) {
int temp = array;
array = array[j];
array[j] = temp;
return 1;
}
}
时间复杂度: T(n) = 2 T(n/2) + O(n) --> T(n) = O(n log n)
空间复杂度: S(n) = O(n)
分享到:
相关推荐
对于给定的数组A,计算其逆序对的总数。即: image.png 【输入形式】 输入包含1组测试用例。 一个测试用例占一行,第一个整数表示...输出一个整数,表示逆序对的个数。 【样例输入】 5 1 2 3 5 4 【样例输出】 4
(1)它的左半部分逆序对的个数,(2)加上右半部分逆序对的个数,(3)再加上左半部分元素大于右半部分元素的数量。 其中前两部分(1)和(2)由递归来实现。要保证算法最后效率O(nlogn),第三部分(3)应该如何...
(2)插入排序的运行时间和数组中逆序对的个数有关系吗?什么关系? 输入格式 第一行:n,表示接下来要输入n个元素,n不超过10000。 第二行:n个元素序列。 输出格式 逆序对的个数。 输入样例 5 2 3 8 6 1 ...
逆序对的个数 输入样例 5 2 3 8 6 1 输出样例 5">设a[0…n 1]是一个包含n个数的数组 若在i<j的情况下 有a[i]>a[j] 则称 i j 为a数组的一个逆序对(inversion) 比如<2 3 8 6 1>有5个逆序对 ...
设A[1..n]是包含n个不同数的数组,如果i而且A[i]>A[j],则(i,j)为一个逆序组,给出时间复杂度为nlgn算法,确定n个任意元素排列中逆序组的个数。
统计数组中的逆序对的个数,基于归并排序的思想,先拆分为单个元素,再合并为两个元素的数组,组内统计后,排序,进行组建统计
输入一个数组,求出这个数组中的逆序对的总数。 示例 1: 输入: [7,5,6,4] 输出: 5 限制: 0 <= 数组长度 <= 50000 来源:力扣(LeetCode) 链接:...
给你m个整数,将其逆序输出 输入 第一行一个整数m(3 ):数的个数 第二行m个整数(空格隔开)(这些数在0-9999999之间) 输出 m个整数(空格隔开
在本步骤开始时空位置的个数是n-(k-1)=n-k+1。我们把k放在从左数的第(bk+1)的空位置上。既然bk≤n-k,因此就有bk+1 ≤n-k+1,从而这样一个空位置就被确定下来了。 ………… n:把n放在剩下的位置上。
今天小编就为大家分享一篇关于Python字符串逆序的实现方法【一题多解】,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧
50006 使用函数统计一个整数中数字的个数 45 50007 使用函数找水仙花数 46 50009 使用函数求余弦函数的近似值 48 50052 使用函数找最大值 49 50062 使用函数输出指定范围内的 Fibonacci 数 50 50063 使用函数找出...
2.4 求一个3*3的矩阵的对角线之和 2.5 将一个数组中的值按逆序重新存放,例如:原来顺序为8,6,5,4,1.要求改为1,4,5,6,8.注:考虑偶数或奇数时怎么交换 2.6 输入十个数,去掉最大数和最小数后求平均值 2.7...
题目:求一个3*3矩阵对角线元素之和 1.程序分析:利用双重for循环控制输入二维数组,再将a[i][i]累加后输出。 【程序26】 题目:有一个已经排好序的数组。现输入一个数,要求按原来的规律将它插入数组中。 ...
# 光棍们对1总是那么敏感,因此每年的11.11被戏称为光棍节。小Py光棍几十载,光棍自有光棍的快乐。 # 让我们勇敢地面对光棍的身份吧,现在就证明自己:给你一个整数a,数出a在二进制表示下1的个数,并输出。 # ...
50006 使用函数统计一个整数中数字的个数 45 50007 使用函数找水仙花数 46 50009 使用函数求余弦函数的近似值 48 50052 使用函数找最大值 49 50062 使用函数输出指定范围内的 Fibonacci 数 50 50063 使用函数找出...
字符分类统计:从键盘输入一行字符串(字符串长度小于等于1000),统计出其中的英文字母、空格、数字和其它字符的个数 题3. 求S=A+AA+AAA+AAAA+….的值,其中,A是0~9范围内的一个数字。输入N和A,其中N表示累加的...
逆序超平面排列与弱布吕阿序,范久瑜,,对每个排列$w$,我们可以根据$w$的逆序构造一个超平面排列$mathcal{A}_w$,称为$w$对应的逆序超平面排列。$mathcal{A}_w$中区域的个数小于等于在
1 字符串最后一个单词的长度 HJ10 字符个数统计 HJ102 字符统计 HJ106 字符逆序 HJ107 求解立方根 HJ108 求最小公倍数 ...HJ13 句子逆序 ...HJ15 求int型正整数在内存中存储时1的个数 HJ2 计算某字符出现次数
4.给一个不多于5位的正整数,要求:一、求它是几位数,二、逆序打印出各位数字。 5.有一分数序列:2/1,3/2,5/3,8/5,13/8,21/13……求出这个数列的前20项之和。 6.打印出杨辉三角形(要求打印出6行如下图) 1 1 1 ...
按之字形顺序打印二叉树,把二叉树打印成多行,把数组排成最小的数,把字符串转化成整数,包含min函数的栈,变态青蛙跳,表示数值的字符串,...数字在排序数组中出现的次数,数组中出现次数超过一半的数字,数组中的逆序对.....