資料結構
網路
關係資料庫管理系統(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 次瀏覽
廣告