生活随笔
收集整理的這篇文章主要介紹了
两种方法求解逆序对
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
逆序?qū)Χx：對(duì)于一個(gè)包含N個(gè)非負(fù)整數(shù)的數(shù)組A[1..n]，如果有i < j，且A[ i ]>A[ j ]，則稱(A[ i] ,A[ j] )為數(shù)組A中的一個(gè)逆序?qū)Α?/strong>
常見的兩種方法求解逆序?qū)?#xff1a;1.窮舉法（暴力求解），時(shí)間復(fù)雜度O（n^2）。2.歸并法， 時(shí)間復(fù)雜度O（nlogn）。
窮舉法：對(duì)于一個(gè)給定的序列，依次從左往右取每一個(gè)元素，從該元素右邊第一個(gè)元素開始向右掃描，遇到比它小的元素，則計(jì)數(shù)+1，直到處理完整個(gè)序列。
#include <iostream>#include <cstdlib>#include <cstdio> using namespace std; #define MAXN 1000int num[MAXN];int sum = 0; void solve(int n){ for(int i = 0; i < n; i++) for(int j = i+1; j < n; j++){ if(num[i] > num[j])sum++;}} int main(int argc, char const *argv[]){ int n; scanf("%d", &n); for(int i = 0; i < n; i++) scanf("%d", &num[i]);solve(n); printf("%d\n", sum); return 0;}
歸并法：將序列A[l..r]分成兩半A[l..mid]和A[mid+1..r]分別進(jìn)行歸并排序，然后再將這兩半合并起來(lái)。
在合并的過程中（設(shè)l<=i<=mid，mid+1<=j<=r），當(dāng)A[i]<=A[j]時(shí)，不產(chǎn)生逆序數(shù)；當(dāng)A[i]>A[j]時(shí)，在
前半部分中比A[i]大的數(shù)都比A[j]大，所以，將A[j]放在A[i]前面的話，逆序數(shù)要加上mid+1-i。因此，可以在歸并排序中的合并過程中計(jì)算逆序數(shù)。
#include <iostream>#include <cstdlib>#include <cstdio> using namespace std; #define MAXN 1000int num[MAXN], temp[MAXN];int sum = 0; void Merge(int l, int mid, int r){ int i = l, j = mid+1, k = l; while(i <= mid && j <= r){ if(num[i] > num[j]){temp[k++] = num[j++];sum += mid-i+1;} elsetemp[k++] = num[i++];} while(i <= mid)temp[k++] = num[i++]; while(j <= r)temp[k++] = num[j++]; for(int i = l; i <= r; i++)num[i] = temp[i]; } void Merge_sort(int l, int r){ if(l < r){ int mid = l + (r-l)/2;Merge_sort(l, mid);Merge_sort(mid+1, r);Merge(l, mid, r);} } int main(int argc, char const *argv[]){ int n; scanf("%d", &n); for(int i = 0; i < n; i++) scanf("%d", &num[i]);Merge_sort(0, n-1); printf("%d\n", sum); return 0;}
附上POJ逆序?qū)Φ囊坏罍y(cè)試題：http://poj.org/problem?id=1804
總結(jié)
以上是生活随笔為你收集整理的两种方法求解逆序对的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
