在数组中,如果 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(largest)在所有排列中插入下一个数字,并在添加这个数字后寻找那些反转计数等于 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]; // 递归函数 int find_permutations (int N_numbers, int K_inversion){ if (N_numbers == 0){ return 0; // 当 N 变为 0 时返回 0 } if (K_inversion == 0) return 1; // 当 K 变为 1 时返回 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; } // 主功能 int main (){ int N, K; cin >> N; // 接受用户的输入 cin >> K; cout << find_permutations (N, K); return 0; }输出结果
0
输入 − N = 4,K = 3
输出 - 6
在这篇文章中,我们解决了一个问题,从O(n * k) 的时间复杂度中找到 K 次反转的排列数。我们还学习了针对这个问题的 C++ 程序以及我们解决这个问题的完整方法(普通和高效)。我们可以用其他语言编写相同的程序,例如 C、java、python 和其他语言。希望这篇文章对您有所帮助。