在数组中，如果 a[i] > a[j] 且 i 排列以完美的 K 反转结束。这是例子 –
Input: N = 4, K = 1Output: 3Explanation: 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 = 2Output : 3Explanation: 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 functionint 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; // taking input from user cin >> K; cout << find_permutations (N, K); return 0;}
输出
0
输入 − N = 4, K = 3
立即学习“C++免费学习笔记（深入）”；
输出 − 6
结论
在本文中，我们解决了一个问题来查找具有 O(n * k) 时间复杂度的 K 个反转的排列。我们还学习了解决这个问题的C++程序以及解决这个问题的完整方法（正常且高效）。我们可以用其他语言比如C、java、python等语言来编写同样的程序。希望这篇文章对您有所帮助。
以上就是使用C++编写代码，找到具有K个逆序对的排列数量的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1444140.html
微信扫一扫 
支付宝扫一扫 
