程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 逆序數及其求法

逆序數及其求法

編輯:關於C語言

 

1. 逆序數

 

所謂逆序數,就是指一個序列S[i],統計處於序列的每個數的比這個數大並且排在它前面的數的數目,然後對於所有數,把這個數目加起來求和就是了。

比如4 3 1 2

4第一個,所以數目為0

3的前面是4,大於3的數目為1

1的前面是4 3 ,大於1的數目為2

2的前面是4 3 1,大於2的數目為2

所以逆序數為1+2+2 = 5

 

求逆序數的兩種方法

常規方法是按照逆序數的規則做,結果復雜度是O(n*n),一般來說,有兩種快速的求逆序數的方法

分別是歸並排序和樹狀數組法

 

 

2. 歸並排序

歸並排序是源於分而治之思想,詳細的過程可以查閱其他資料,總體思想是劃分一半,各自排好序後將兩個有序序列合並起來。

 

如何修改歸並排序求逆序數?

首先我們假設兩個有序序列a[i]和b[i],當合並時:

由於a[i]已是有序,所以對於a[i]的各個元素來說,排在它前面且比它大的數目都是0

當b[i]中含有比a[i]小的元素時,我們必然將b[i]元素插到前面,那麼就是說,在b[i]原先位置到該插的位置中,所有數都比b[i]大且排在它前面

所以這是b[i]的數目為新插入位置newPos - 原來位置oldPos

 

那麼對於一半的序列又怎麼做呢?我們知道,歸並排序會繼續向下遞歸,而遞歸完成返回後將是兩組有序的序列,並且拿到局部的逆序數,

所以在Merge函數中添加這一計數操作即可

 

 

 

 

代碼示例如下:int L[M];

int R[M];

 

const int Max = 1 <<30;

__int64 change = 0;

 

void Merge(int *data,int left,int divide,int right)

{

    int lengthL = divide - left;

    int lengthR = right - divide;

   

    for(int i = 0; i < lengthL; ++i)

    {

        L[i] = data[left + i];

    }

    for(int i = 0; i < lengthR; ++i)

    {

        R[i] = data[divide + i];

    }

    L[lengthL] = R[lengthR] = Max;

    int i = 0;

    int j = 0;

    for(int k = left; k < right; ++k)

    {

        if(L[i] <= R[j])

        {

            data[k] = L[i];

            ++i;

        }

        else

        {

            change += divide - i - left ;

            data[k] = R[j];

            ++j;

        }

    }

 

}

 

void MergeSort(int *data,int left,int right)

{

    if(left < right -1)

    {

        int divide = (left + right)/2;

        MergeSort(data,left,divide);

        MergeSort(data,divide,right);

        Merge(data,left,divide,right);

    }

}

 

 

3. 樹狀數組

求逆序數的另外一種方法是使用樹狀數組

對於小數據,可以直接插入樹狀數組,對於大數據,則需要離散化,所謂離散化,就是將

100 200 300 400 500 ---> 1 2 3 4 5

 

這裡主要利用樹狀數組解決計數問題。

 

首先按順序把序列a[i]每個數插入到樹狀數組中,插入的內容是1,表示放了一個數到樹狀數組中。

然後使用sum操作獲取當前比a[i]小的數,那麼當前i - sum則表示當前比a[i]大的數,如此反復直到所有數都統計完,

比如

4 3 1 2

i = 1 : 插入4 : update(4,1),sum(4)返回1,那麼當前比4大的為i - 1 = 0;

i = 2 : 插入3 : update(3,1),sum(3)返回1,那麼當前比3大的為i - 1 = 1;

i = 3 : 插入1 : update(1,1),sum(1)返回1,那麼當前比1大的為i - 1 = 2;

i = 4 : 插入2 : update(2,1),sum(2)返回2,那麼當前比2大的為i - 2 = 2;

 

過程很明了,所以逆序數為1+2+2=5

 

代碼示例如下:

 

//樹狀數組

__int64 sums[1005];

int len;

 

inline int lowbit(int t)

{

    return t & (t^(t-1));

}

 

void update(int _x,int _value)

{

    while(_x <= len)

    {

        sums[_x] += _value;

        _x += lowbit(_x);

    }

}

 

__int64 sum(int _end)//get sum[1_end]

{

    __int64 ret = 0;

    while(_end > 0)

    {

        ret += sums[_end];

        _end -= lowbit(_end);

    }

    return ret;

}

 

//求逆序數

 

__int64 ret = 0;

for (__int64 i = 0; i < k; ++i)

{

    update(a[i],1);

    ret += (i+1) - sum(a[i]);

}

 

 

求逆序數的題目有:

http://poj.org/problem?id=2299

http://poj.org/problem?id=3067

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved