1,这个问题算法导论讲归并排序时,提到过。
找到一个实现代码,思路还是蛮清晰的。
核心:对于两个有序序列,找逆序对,遍历一次即可。
2,实现代码:
#include <iostream>
#include <cstring>
using namespace std ;
int inv(int data[], int n)
{
int left = (n >> 1);
int right = n - left;
int *tmp = new int[n];
int ret = (right > 1? (inv(data, left) + inv(data + left, right)) : 0);
int i = 0, j = 0;
while (i < left)
{
while ((j < right) && ((i == left || data[i] > data[left + j]))) //核心,实质遍历一次即可
//因为这个时候左右两边都是有序的
{
tmp[i + j] = data[left + j]; //这里由于逆序,存放后右边的
j++; //有序的,所有后一个数的逆序数肯定大于前一个的
}
ret += j;
tmp[i + j] = data[i]; //不是逆序,存放左边的
i++;
}
memcpy(data, tmp, sizeof(int) * n);
delete[] tmp;
return ret;
}
int main()
{
int data[] = {5, 4, 3, 2, 1};
cout << inv(data, sizeof(data)/sizeof(data[0])) << endl;
return 0;
}
分享到:
相关推荐
本篇文章主要探讨如何使用递归算法来实现一个整数的逆序操作,即把一个数字的位数顺序反转过来。例如,将数字1234转换为4321。 #### 知识点概述 1. **递归算法的概念** 2. **递归的基本要素** 3. **递归与循环的...
在编程领域,数组的逆序排列是一个常见的操作,特别是在数据处理和算法实现中。这个题目要求我们编写一个程序,将一个包含8个整数的一维数组进行逆序排列。逆序排列意味着数组原来的顺序被反转,例如,如果原始数组...
编写一个程序,输入一个整数数组,计算并输出数组的平均值。 示例输入:5 1 2 3 4 5 示例输出:3.00 斐波那契数列 编写一个程序,输入一个正整数n,输出斐波那契数列的前n项。 示例输入:5 示例输出:0 1 1 2 3
5. 写一个程序,判断一个数是否是回文数 6. 写一个程序,判断一个字符串是否是回文字符串 7. 写一个程序,生成一个随机数并将其逆序输出 8. 写一个程序,求两个数的最大公约数 9. 写一个程序,求两个数的最小公倍数 ...
40027 从高位开始逐位输出一个整数的各位数字(选作) 39 40052 判断素数 40 40053 逆序输出整数 41 40054 输出斐波那契序列 42 第7周(M7) 42 50002 使用函数判断数的符号 42 50003 使用函数求奇数和 43 50005 使用...
质数的判断方法是通过遍历一个数的所有小于它的正整数,检查是否存在除了1和它自身以外的因数。 ```javascript var count = 0; // 计数器 for (var i = 1; i ; i++) { // 看每个i是否质数 for (var j = 1; j ; j+...
* 整数转换为字符,再逆序输出问题:该问题要求学生编写一个C语言程序来将一个整数转换为字符,然后逆序输出,例如输入123,输出应该是321。 * 输出由*号组成的一个三角形问题:该问题要求学生编写一个C语言程序来...
- 描述:从键盘输入一个字符串,将这个字符串变成逆序字符串并输出。 - 关键知识点: - 输入输出操作:使用`scanf`接收字符串,使用`printf`输出逆序字符串。 - 字符串操作:遍历字符串并反转字符顺序。 - **...
1.7 有一个数,内放10个数,不用全局变量求出最大值,最小值,和平均值。 1.8 用调用函数求最大公约数和最小公倍数。两个整数由键盘输入 1.9 写出一个判素数的函数,在主函数输入一个整数,输出是否为素数的信息 ...
我们可以使用循环结构,从1开始遍历到给定的数N,检查每个数是否满足条件并打印出来。 【数据输入和输出】 - 输入:每个问题都有其特定的输入格式,如逆序数字需要输入测试案例数量T和N,人见人爱A+B需要N个6位整数...
1. 如果两个数中有任何一个是0,则返回另一个数作为最大公约数。 2. 将较大的数与较小的数进行比较,并进行取模操作。 3. 重复以上步骤,直到模运算的结果为0。 代码实现如下: ```cpp int Gcd(int m, int n) { ...
4. **求和与逆序输出**:程序读取10个整数并累加得到总和`sum`,然后逆序输出这10个数。第一个for循环负责累加,第二个for循环用于输出总和,第三个for循环则逆序输出数组元素。结果是10个整数的总和和逆序后的数组...
可以编写一个函数判断一个数是否为回文数,通过比较数的前半部分与后半部分是否相等来实现。 7. **计算年、月、日**:这需要理解日期计算,可以通过累加每月天数来求解。 8. **求特定数列和**:对于数列求和问题,...
当只传入一个参数如`rst(5)`时,`b`使用默认值,所以计算结果为`5*5`,输出`25`。 3. **函数无返回值**: 在`jsarea(r, PI = 3.14)`函数中,虽然进行了计算但没有`return`语句,这意味着函数调用将返回`None`。...
当输入的整数 `n_` 等于1时,返回1,否则返回 `n_` 乘以 `fun1(n_-1)`,即 `n_` 的前一个数的阶乘。递归的核心在于函数调用自身,并且每个递归调用都有一个更简单的基本情况,这里是 `n_ == 1`。 - `fun2` 函数是...
题目要求找到一个三位数,其每一位数字的阶乘之和等于该数本身。这涉及到循环遍历三位数范围,计算阶乘,并进行条件判断。这里的知识点包括循环、取模运算、除法运算、条件判断以及阶乘的计算。 3. **斐波那契数列...
4. 同构数的查找:遍历1到99,检查每个数是否在其平方数的右边,这涉及到幂运算和字符串比较。 5. "水仙花数"的输出:对于n位的水仙花数,需要计算每位数字的n次方和,判断是否等于原始数字。 6. 回文数的寻找:...
11. **小于六位,逆序输出**:这个题目要求读取一个数,如果它小于六位,就将它倒序输出。这需要用到字符串处理和转换数字为字符串的功能。 12. **求 5+...+55555 的和**:这是一个简单的等差数列求和问题,可以用...
- `link` 数组用于记录最长不下降子序列的前一个元素的位置,以便后续可以逆序输出最长不下降子序列; - `result` 用于记录最长不下降子序列的长度; - `cur` 用于记录最长不下降子序列的最后一个元素的位置。 **...
一个程序计算输入数字的位数,另一个不仅计算位数,还将数字逆序输出。 8. **打印水仙花数**:第九个程序遍历100到999之间的所有数字,寻找满足条件的水仙花数,即数字的每一位立方和等于原数的数字。 9. **判断...