-
逆序對
鎖定
逆序對，數學術語，設 A 為一個有 n 個數字的有序集 (n＞1)，其中所有數字各不相同。
如果存在正整數 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，則 這個有序對稱為 A 的一個逆序對，也稱作逆序數。
- 中文名
- 逆序對
- 外文名
- Count Inversions
- 問題描述
- 一個數組，求數組中多少個逆序對
- 求解方法
- 利用兩重循環進行枚舉或歸併排序
逆序對定義
對於一個包含N個非負整數的數組A[1..n]，如果有i < j，且A[ i ]>A[ j ]，則稱(A[ i] ,A[ j] )為數組A中的一個逆序對。
例如，數組（3，1，4，5，2）的逆序對有(3,1),(3,2),(4,2),(5,2)，共4個。
逆序對求解
問題描述
給定一個數組，求該數組中包含多少個逆序對。
求解方法
方法一：最原始的方法，利用兩重循環進行枚舉。該算法的時間複雜度為O(n^2)。
C++代碼如下：
int count_inversion(int a[], int n)
{
int count = 0;
for(int i = 0; i < n - 1; ++i)
for(int j = i + 1; j < n; ++j)
if(a[i] > a[j]) count += 1;
return count;
}
Pascal代碼如下：
var i,j,k,n:longint; a:array[1..1000000] of longint; begin readln(n); for i:=1 to n do read(a[i]); k:=0; for i:=1 to n-1 do for j:=i+1 to n do if a[i]>a[j] then inc(k); writeln(k); end.
C++代碼如下：
#include <bits/stdc++.h>
using namespace std;
// [l, r)
void merge_inversion(vector<int> &nums, int l, int r, int &cnt)
{
cout << l << " - " << r << endl;
// 只有一個元素直接返回
if(r - l <= 1 ) return;
// 分治
int m = l + (r - l) / 2;
merge_inversion(nums, l, m, cnt);
merge_inversion(nums, m, r, cnt);
// 歸併, 按照從大到小的順序。
int i = l;
int j = m;
vector<int> temp;
for(int k = l; k < r; ++k) {
if(i < m && j < r)
if(nums[i] > nums[j]) {
cnt += (r - j);
temp.push_back(nums[i++]);
}
else temp.push_back(nums[j++]);
else {
if(i < m) temp.push_back(nums[i++]);
else if(j < r) temp.push_back(nums[j++]);
}
}
for(int k = l; k < r; ++k)
nums[k] = temp[k - l];
}
int main()
{
vector<int> nums = {1, 7, 2, 5, 8, 10, 6};
int ans = 0;
merge_inversion(nums, 0, nums.size(), ans);
cout << ans << endl;
for(int i = 0; i < nums.size(); ++i)
cout << nums[i] << " ";
cout << endl;
return 0;
}
Pascal代碼如下：
Type arr=array[1..1000000]of longint; Var i,n:longint; k:int64; a,b:arr; Procedure merge(var a:arr;l,x,r:longint); var i,j,p:longint;//p:position begin i:=l; j:=x+1; p:=l; while (p<=r) do begin if(i<=x)and((j>r)or(a[i]<=a[j])) then begin b[p]:=a[i]; inc(i); end else begin b[p]:=a[j]; inc(j); inc(k,x-i+1); end; inc(p); end; for i:=l to r do a[i]:=b[i]; end; Procedure msort(var a:arr;l,r:longint); var x:longint; begin if (l<>r) then begin x:=(l+r)div 2; msort(a,l,x); msort(a,x+1,r); merge(a,l,x,r); end; end; Begin readln(n); for i:=1 to n do read(a[i]); k:=0; msort(a,1,n); writeln(k); End.
方法三：利用樹狀數組求逆序對，開始先將序列離散化以提高算法的時空效率，然後從序列的最左端開始建立樹狀數組，每創建一個就執行一次 i - getsum( x ) (x 為離散化的 值) 累加到ans上。最後的 ans即為所求的答案。注意在進行排序的時候如果兩個數組的值相等, 則需要確保排序後原先的相對順序不發生改變, 即確保使用穩定的排序方式。
該算法的時間複雜度為O(nlogn)。
C++代碼如下：
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000
int b[MAXN]; /* 離散化後的數組*/
int c[MAXN]; /* 存儲樹狀數組的元素*/
int n; /* 數組的元素的個數*/
struct Node
{
int val, i;
bool operator < (const Node& rhs) const {
return (this->val < rhs.val) || (this->val == rhs.val && this->pos < rhs.pos);
}
}a[MAXN]; /* 存放原數組元素, 並帶有其在元素組當中的位置*/
int lowbit(int i)
{
return i & (-i);
}
void update(int i, int val)
{
while(i <= n) {
c[i] += val;
i += lowbit(i);
}
}
int getSum(int i)
{
int res = 0;
while(i > 0) {
res += c[i];
i -= lowbit(i);
}
return res;
}
int main()
{
// 輸入原數組
cin >> n;
for(int i = 1; i <= n; ++i)
cin >> a[i].val, a[i].i = i;
// 對原數組按照val大小排序, 則此時的 i 的順序就是離散後的數組
sort(a + 1, a + 1 + n);
// 計算逆序對
int ans = 0;
for(int i = 1; i <= n; ++i) {
cout << a[i].val << " - " << a[i].i << endl;;
update(a[i].i, 1);
ans += a[i].i - getSum(a[i].i);
}
cout << ans << endl;
return 0;
}
