배열에서 A 쌍 a[i], a[j]는 a[i]> a[j] 및 i
무차별 대입 접근 방식을 적용할 수 있습니다. , 먼저 처음 N 숫자의 모든 순열을 찾은 다음 K와 같은지 여부를 모든 반전을 확인합니다. 그렇다면 결과 카운터를 증가시킵니다.
이 접근 방식에서는 처음 N개의 자연수 중 N자리가 있습니다. 해당 숫자의 모든 순열은 K 순열을 찾는 다른 곳에서 계산됩니다. 그것을 찾기 위해 우리는 모든 순열에서 다음 숫자 N번째(가장 큰)를 삽입하고 이 숫자를 추가한 후 반전 횟수가 K와 같은 숫자를 찾고 결과에 계산되어야 합니다. (K – 3) 반전이 없는 (N – 1) 숫자의 이러한 순열을 취하면 마지막 인덱스에서 세 번째 인덱스의 새 숫자를 이동합니다. 반전의 수는 K가 될 것이며 find_permutations(N-1, K-3)가 답이 될 것입니다. 다른 반전에도 동일한 논리를 사용할 수 있으며 최종 답은 위의 재귀에 도달합니다.
입력 - N =4, K =3
출력 - 6
이 기사에서는 O(n * k)에서 K 역전이 있는 순열의 수를 찾는 문제를 해결합니다. 시간 복잡도. 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결하는 완전한 접근 방식( Normal 및 Efficient)을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.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.
해결 방법 찾기
효율적인 접근
입력
#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
결론
