使用C++编写代码，找到具有K个逆序对的排列数量

prtyaa 2024-01-08 23:21:36  64194 赞同 0 反对 0

分类：资源标签：运维

使用C++编写代码，找到具有K个逆序对的排列数量

在数组中，如果 a[i] > a[j] 且 i

Input: N = 4, K = 1
Output: 3
Explanation: Permutation of the first N numbers in total : 1234, 1243, 1324 and 2134. With 1 inversion we have 1243, 1324 and 2134.

Input : N = 3, K = 2
Output : 3
Explanation: Permutation of the first N numbers in total : 123, 132, 213, 231, 312, and 321 with 2 inversions we have 231, 312 and 321.

求解的方法

我们可以采用蛮力法，首先找到前N个数的所有排列，然后检查所有的反转是否相等是否K。如果是，则增加结果计数器。

高效方法

在这种方法中，我们有前 N 个自然数的 N 位。该数字的所有排列都是在其他地方计算的，我们从中寻找 K 个排列。为了找到它，我们将在所有排列中插入下一个数字 Nth（最大），并在添加该数字后查找反转计数等于 K 的数字应计入我们的结果中。采用没有 (K – 3) 个反转的 (N – 1) 个数字的排列，我们将在最后一个索引的第三个索引处移动新数字。反转次数为 K，find_permutations(N-1, K-3) 将是我们的答案。相同的逻辑可以用于其他反转，我们将得到上述递归作为最终答案。

输入

#include
using namespace std;
const int X = 100;
int a = 0;
int arr[X][X];
// recursive function
int find_permutations (int N_numbers, int K_inversion){
if (N_numbers == 0){
return 0; // return 0 when N becomes 0
}
if (K_inversion == 0)
return 1; // return 1 when K becomes 1
if (arr[N_numbers][K_inversion] != 0)
return arr[N_numbers][K_inversion];
int result = 0;
for (int i = 0; i N; // taking input from user
cin >> K;
cout

如果您发现该资源为电子书等存在侵权的资源或对该资源描述不正确等，可点击“私信”按钮向作者进行反馈；如作者无回复可进行平台仲裁，我们会在第一时间进行处理！

评价 0 条

相关资源

如何利用C++进行高效的图像处理和图像分析？ 2024-01-09 64594 浏览
如何利用C++进行高效的图像处理和图像分析？图像处理和分析是计算机视觉领域中非常重要的任务，它涉及到图像的获取、处理、分析和理解。而C++作为一种高性能的编程语言，能够提供丰富的图像处理和分析库，使得我们能够快速、高效地进行图像处理和分析工作。本文将介绍如何利用C++进行高效的图像处理和图像分析，并给出相应的代码示例。
C++ module编程升级指南,子模块与分区全解析 2024-01-08 67126 浏览
子模块 1.C++ 标准与子模块 C++ 标准并没有特别提到子模块，但允许在模块名称中使用点（.），从而可以按任何你想要的层次结构来组织模块。例如，以下是一个 DataModel 命名空间的示例：
C++是不是类型安全的? 2024-01-08 67220 浏览
1. 什么是类型安全类型安全(Type Safety)是指语言在编译和运行时提供的保护机制,来避免出现非法的类型转换和操作。
C++11中auto关键字的使用详解 2024-01-08 66401 浏览
C++11标准带来了很多新特性，其中auto关键字的引入，极大地提高了编程的便利性和代码的可读性。本文将通过实例详解auto关键字的使用。
C++ extern的用法详细解析 2024-01-08 66992 浏览
C++编程中，extern是一个非常重要的关键字，它的用途主要是用来声明一个全局变量或者函数。本文将详细解析extern的用法，并通过实例进行详细的解释。
C++中getline函数多种定义的使用方法 2024-01-08 62799 浏览
getline()函数是一个相当常见的工具，用于从输入流中获取一行数据。
使用C++编写的矩阵中找到具有最大和的一对的算法 2024-01-08 68418 浏览
在本文中，我们将讨论在给定矩阵或二维数组中查找具有最大和的对。例如
名称混淆和extern "C"在C++中 2024-01-08 66683 浏览
在C++中我们可以使用函数重载特性。利用这个特性，我们可以创建同名的函数。唯一的区别是参数的类型和参数的数量。这里不考虑返回类型。现在的问题是，C++如何区分目标代码中的重载函数？
使用C++编写一个找到数字的程序，其数字的各位数之和为偶数的程序 2024-01-08 67742 浏览
能被2整除的整数是偶数。因此在本文中，我们给定了一个数n，我们需要找到第n个数字，其数字之和为偶数。前五个数字的数字之和为偶数的数分别是2、4、6、8和11。例如 −
C/C++模块方程解的程序 2024-01-09 66300 浏览
在数学中，模方程是模问题意义上满足模的代数方程。也就是说，给定模空间上的多个函数，模方程是它们之间的方程，或者换句话说，模恒等式。

使用C++编写代码，找到具有K个逆序对的排列数量

求解的方法

高效方法

输入

相关资源

关注我们