posts - 33,  comments - 33,  trackbacks - 0

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

posted on 2011-11-17 20:46 bennycen 阅读(10699) 评论(0)  编辑 收藏 引用 所属分类: 算法题解

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理