数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学使用C++查找具有K个逆序对的排列数
在一个数组中，如果a[i] > a[j]且i < j，则称a[i], a[j]为一个逆序对。我们有两个数字N和k，需要计算前N个数字有多少种排列恰好有K个逆序对。
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)个数字的排列，我们将新数字插入到从末尾算起的第3个索引处。逆序对的数量将为K，`find_permutations(N-1, K-3)`将是我们的答案。相同的逻辑可以用于其他逆序对，最终我们将得到上述递归作为最终答案。
输入
#include <bits/stdc++.h>
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 <= K_inversion; i++){
if (i <= N_numbers - 1)
result += find_permutations (N_numbers - 1, K_inversion - i);
}
arr[N_numbers][K_inversion] = result;
return result;
}
// main function
int main (){
int N, K;
cin >> N; // taking input from user
cin >> K;
cout << find_permutations (N, K);
return 0;
}输出
0
输入 − N = 4, K = 3
输出 − 6
结论
在这篇文章中，我们解决了一个问题，即找到具有K个逆序对的排列数，时间复杂度为**O(n * k)**。我们还学习了这个问题的C++程序以及我们用来解决这个问题的完整方法（常规和高效方法）。我们可以用C、Java、Python和其他语言编写相同的程序。希望本文对您有所帮助。
更新于：2021年11月24日
316 次浏览
广告