精华内容
下载资源
问答
  • 算法导论学习1--分治法计算逆序数

    千次阅读 2011-09-06 00:43:34
    看到了2-4,习题,计算逆序数的问题,忍不住实现了一下。   逆序数,是排列组合中常见的一个指标,可以用来衡量一个数列的杂乱成对(相对于顺序排列),在一些算法如水印算法中有广泛的应用。 如此如何快速的求得...

     闲来无事,复习复习经典的算法导论。看到了2-4,习题,计算逆序数的问题,忍不住实现了一下。

     

    逆序数,是排列组合中常见的一个指标,可以用来衡量一个数列的杂乱成对(相对于顺序排列),在一些算法如水印算法中有广泛的应用。 如此如何快速的求得任意序列的逆

    序数是关心的重点。常见的一种高效解法,是devid - and -conqure. 将序列平分成两段,分别计算逆序数,然后将两个有序的数列进行归并,并在归并过程中求取逆序数。两个

    子序列的逆序数求取是较小规模的同样问题,可以用递归的方式完成。

     

    简单说下如何在归并的过程中,计算逆序数。假设,有一个序列array[p, mid, r]. 其中array[p...mid], array[mid+1, ..., r]已经分别从小到大排好序。下面我们将两个子序列进行归

    并。  假设当前的右边子序列(array[mid+1, ...., r])的当前待比较元素下表为right, 左边的为left, 当array[left] <= array[right], 这时候没有逆序发生(因为left的数 比right的

    大)。当array[left] > array[right], 是,right指向的元素具有逆序数,个数为他之前的所有的数,即mid-left+1。如此遍历下去,即可得到在归并中得到逆序数。

     

    算法非常简单直白。 复杂度为: T(n) = 2T(n/2) + O(n).  根据master定理, T(n) = O(nlogn). 空间复杂度为2n,当然可以更小,2logn。

     

    附上java实现的源代码。

     

    public class MergInversionCount {
    	public static int count(int[] array, int p, int r) {
    		int inversionCount = 0;
    		if (p < r) {
    			int mid = (p + r) / 2;
    			inversionCount += count(array, p, mid);
    			inversionCount += count(array, mid+1, r);
    			inversionCount += mergeInversion(array, p, mid, r);
    		}
    		return inversionCount;
    	}
    
    	private static int mergeInversion(int[] array, int p, int mid, int r) {
    		int inversionCount = 0;
    		int[] temp = new int[r-p+1];
    		if(array.length < r)
    			return inversionCount;
    		int left = p;
    		int right = mid + 1;
    		int storeIndex = 0;
    		while(left <= mid && right <= r)
    		{
    			if(array[left] > array[right])
    			{
    				inversionCount += mid-left+1; //当前right存在逆序数,数目等于mid-left+1
    				temp[storeIndex] = array[right];
    				right++;
    			}
    			else
    			{
    				temp[storeIndex] = array[left];
    				left++;
    			}
    			storeIndex++;
    		}
    		if(left <= mid)
    		{
    			for(int i = left; i <= mid; i++)
    			{
    				temp[storeIndex] = array[i];
    				storeIndex++;
    			}
    		}
    		if(right <= r)
    		{
    			for(int i = right; i <= r; i++)
    			{
    				temp[storeIndex] = array[i];
    				storeIndex++;
    			}
    		}
    		
    		for(int i = p; i <= r; i++)
    		{
    			array[i] = temp[i-p];
    			
    		}
    		return inversionCount;
    	}
    
    }
    
    
    
    import static org.junit.Assert.*;
    
    import org.junit.Test;
    
    public class MergInversionCountTest {
    
    	@Test
    	public void testCount() {
    		int[] array = {1,5,6,7,4};
    		int[] array2 = {1,5,6,7,4,3,11, 15, 13, 2, 8};
    		
    		int inversionCount = MergInversionCount.count(array, 0, 4);
    		assertTrue(inversionCount == 3 );
    		
    		inversionCount = MergInversionCount.count(array2, 4, 10);
    		assertTrue(inversionCount == 10 );
    
    	}
    
    }


     

     

     

    展开全文
  • 如何求一组数的逆序数

    千次阅读 2014-01-18 09:59:24
    *方案一(1)对数组中的每个数计算逆序数,之后再加和,得出整个数组的逆序数,复杂度O(n^2) *方案二(2)借助归并排序的思想求解 */ #include #include int compute1(int *begin, int *end) { int *p, *q; ...
    /**
    *求一组数的逆序数
    *方案一(1)对数组中的每个数计算逆序数,之后再加和,得出整个数组的逆序数,复杂度O(n^2)
    *方案二(2)借助归并排序的思想求解,复杂度O(nlogn)
    */
    
    #include <stdio.h>
    #include <malloc.h>
    
    int compute1(int *begin, int *end)
    {
        int *p, *q;
        int sum1, sum = 0;
        for(p = begin; p < end; p++)
        {
            sum1 = 0;
            for(q = p + 1; q <= end; q++)
            {
                if(*p > *q)
                    sum1++;
            }
            sum += sum1;
            printf("%d\n",sum1);
        }
    
        return sum;
    }
    
    int compute2(int *begin, int *end)
    {
        int sum = 0, i = 0;
        int *middle, *lbegin, *rbegin, *temp;
        int lsum, rsum;
    
        if(end - begin == 0)
            return 0;
    
        if(end - begin >= 1)
        {
            middle = begin + (end - begin) / 2;
    
            lsum = compute2(begin, middle);
            rsum = compute2(middle + 1, end);
    
            lbegin = begin;
            rbegin = middle + 1;
            temp = (int *)malloc(sizeof(int) * (end - begin + 1));
            while(lbegin <= middle && rbegin <= end)
            {
                if(*lbegin > *rbegin)
                {
                    temp[i] = *rbegin;
                    i++;
                    rbegin++;
                    sum += (middle - lbegin + 1);
                }
                else
                {
                    temp[i] = *lbegin;
                    i++;
                    lbegin++;
                }
            }
            while(lbegin <= middle)
            {
                temp[i] = *lbegin;
                lbegin++;
                i++;
            }
            while(rbegin <= end)
            {
                temp[i] = *rbegin;
                rbegin++;
                i++;
            }
    
            i = 0;
            while(begin <= end)
            {
                *begin = temp[i];
                begin++;
                i++;
            }
    
            return sum + lsum + rsum;
        }
    
    }
    
    int main()
    {
        int a[10] = {2,4,56,12,76,23,56,223,4,45};
        printf("数组a的逆序数为%d\n",compute1(a, a + 9));
    
        printf("数组a的逆序数为%d\n",compute2(a, a + 9));
    
        return 0;
    }
    

      关于归并排序也可参考:http://blog.csdn.net/sjyu_ustc/article/details/10085343

    展开全文
  • 如果只是八数,暴力解法还好,当数字多了之后如何知道逆序数呢。 题目描述 通过计算八数码节点的逆序数判断。如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序...

    在求解八数码问题时,因为要进行逆序数的计算判断两个结点的可达性,同奇偶的逆序数才能可达。如果只是八数,暴力解法还好,当数字多了之后如何知道逆序数呢。

    题目描述

    通过计算八数码节点的逆序数判断。如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。逆序数为偶数的排列称为偶排列;逆序数为奇数的排列称为奇排列。如 2431 中,21,43,41,31 是逆序,逆序数是 4,为偶排列。
    计算八数码节点的逆序数时将代表空格的 0 去除,如初始状态排列为 (1,3,2,4,5,6,7,8) 逆序数为:0+1+0+0+0+0+0+0=1 即为奇排列
    目标状态排列为(1,2,3,8,4,7,6,5) 逆序数0+0+0+4+0+2+1+0=7 即为奇排列,具有同奇或同偶排列的八数码才能移动可达,否则不可达。

    思路一

    暴力穷举,每次扫描一个数时,遍历后方所有的数,那么这样的代价很大,O(n2)的时间复杂度。

    思路二

    分治的思想,自上而下划分,将大数组划分为小数组,只到划分到为数组中只有一个时,通过自下而上的排序的过程,计算出本数组中的数与相邻数组的逆序数,其实本质就是归并排序的过程。时间复杂度nlog2n。
    在这里插入图片描述
    那么怎么在归并排序的过程中进行分组呢?
    例如下方,先考察相邻数组块的最大值,比较后若左侧大于右侧,则逆序数加上右侧剩余数目(因为两侧数据皆为有序),并加大数填入最终的位置,并将大数所在数组指针向右侧移动。直到指针全部移到最左端。当一侧的数据全部填入之后,将剩余部分填入最前端。
    在这里插入图片描述

    代码实现

    作为数组,可以省略“分”的步骤,看成已经将每个数分成一个单位,直接进行“治”的过程。

    `int sort(int *b, int start,int step,int num)//排序相邻的数据块
    {
    	int result = 0;
    	if (start + step >= num)//如果是最后只剩一个数组块,不需要比较排序
    	{
    		return 0;
    	}
    	else//如果最后剩余两个数组块
    	{
    		int c[20];//临时保存最终排序完成的数组,从大到小排列,共rightend-leftend+1个元素
    		int n = 0;
    		int leftstart = start;
    		int leftend = start + step - 1;//前一个数组的起始和最后
    		int rightstart = start + step;
    		int rightend;//后一个数组的起始和最后
    		if (start + 2 * step > num)//最后一个数组块不足step个
    		{
    			rightend = num-1;
    		}
    		else//两个比较的数据块相同个数都为step个 
    		{
    			rightend = start + 2 * step - 1;
    		}
    		int left = leftend;
    		int right = rightend;
    		while (left>=leftstart&&right>=rightstart)
    		{
    			if (b[left] < b[right])
    			{
    				c[n++] = b[right];
    				right--;
    			}
    			else
    			{
    				c[n++] = b[left];
    				left--;
    				result += right - rightstart + 1;
    			}
    		}
    		int begin = start;
    		if (left >= leftstart)//最小的一部分在左侧
    		{
    			begin = left + 1;
    		}
    		else//最小的一部分在右侧
    		{
    			for (int i = rightstart; i <= right; i++)
    			{
    				b[begin++] = b[i];
    			}
    		}
    		for (int i = begin; i <= rightend; i++)
    		{
    			b[i] = c[--n];
    		}
    		return result;
    	}
    
    }
    int inverse_number(int *a, int num)//归并排序
    {
    	int b[20];
    	for (int i = 0; i < num; i++)
    	{
    		b[i] = a[i];
    	}
    	int sum = 0;
    	int step = 1;
    	while (step < num)
    	{
    		for (int i = 0; i < num; i =i + 2*step)
    		{
    			sum += sort(b, i, step,num);
    		}
    		step = step * 2;
    	}
    	return sum;
    }`
    

    优化

    当经过一轮排序,所有数据未发生改变即可停止。

    展开全文
  • 奇数码问题 Page38 归并排序计算逆序对 逆序对问题树状数组也可解决 如何转化为逆序对的奇偶性问题?? 证明: 空格的水平移动不会影响逆序对数 空格的上下移动会将一个xxx与空格交换,即将xxx移动到n−1n-1n−1个...

    奇数码问题 Page38 归并排序计算逆序对

    逆序对问题树状数组也可解决

    如何转化为逆序对的奇偶性问题??
    证明
    空格的水平移动不会影响逆序对数
    空格的上下移动会将一个数xx与空格交换,即将xx移动到n1n-1个元素之后或之前。
    现在假设移动到n1n-1个元素之前
    假设这n1n-1个元素中有kk个比xx小,那么移动之后逆序对数变化量为(n1k)k=n12k|(n-1-k)-k|=|n-1-2k|n1n-1为偶数,2k2k也为偶数,故逆序对变化量也为偶数。

    代码过于繁琐了,就当水篇博客
    代码

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #include<string>
    #include<vector>
    #include<stack>
    #include<bitset>
    #include<cstdlib>
    #include<cmath>
    #include<set>
    #include<list>
    #include<deque>
    #include<queue>
    #include<map>
    #define ll long long
    #define pb push_back
    #define rep(x,a,b) for (int x=a;x<=b;x++)
    #define repp(x,a,b) for (int x=a;x<b;x++)
    #define W(x) printf("%d\n",x)
    #define WW(x) printf("%lld\n",x)
    #define pi 3.14159265358979323846
    #define mem(a,x) memset(a,x,sizeof a)
    #define lson rt<<1,l,mid
    #define rson rt<<1|1,mid+1,r
    using namespace std;
    const int maxn=2e6+7;
    const int INF=1e9;
    const ll INFF=1e18;
    int a[maxn],b[maxn],aa[maxn],n,m,x;
    ll cnt1,cnt2;
    void merge1(int l,int r)
    {
        int mid=(l+r)>>1;
        int i=l,j=mid+1;
        rep(k,l,r)
        {
            if (j>r||i<=mid&&a[i]<=a[j])b[k]=a[i++];
            else b[k]=a[j++],cnt1+=mid-i+1;
        }
        rep(k,l,r)a[k]=b[k];
    }
    void merge2(int l,int r)
    {
        int mid=(l+r)>>1;
        int i=l,j=mid+1;
        rep(k,l,r)
        {
            if (j>r||i<=mid&&aa[i]<=aa[j])b[k]=aa[i++];
            else b[k]=aa[j++],cnt2+=mid-i+1;
        }
        rep(k,l,r)aa[k]=b[k];
    }
    void merge_sort1(int l,int r)
    {
        int mid=(l+r)>>1;
        if (l<r)
        {
            merge_sort1(l,mid);
            merge_sort1(mid+1,r);
            merge1(l,r);
        }
    }
    void merge_sort2(int l,int r)
    {
        int mid=(l+r)>>1;
        if (l<r)
        {
            merge_sort2(l,mid);
            merge_sort2(mid+1,r);
            merge2(l,r);
        }
    }
    int main()
    {
        while(~scanf("%d",&n)&&n)
        {
            cnt1=0;cnt2=0;m=1;
            rep(i,1,n)
            {
                rep(j,1,n)
                {
                    scanf("%d",&x);
                    if (x!=0)a[m++]=x;
                }
            }
            m=1;
            rep(i,1,n)
            {
                rep(j,1,n)
                {
                    scanf("%d",&x);
                    if (x!=0)aa[m++]=x;
                }
            }
            merge_sort1(1,n*n-1);
            merge_sort2(1,n*n-1);
            if (cnt1%2==cnt2%2)printf("TAK\n");
            else printf("NIE\n");
        }
        return 0;
    }
    
    展开全文
  • 这道题对于C语言初学者来说,...按逆序输出各位数字,例如原为321,应输出123。 先看第一问,求n是几位数,n的取值可以是5,4,3,2,1。N的值如何得到呢,可以通过如下循环来实现: int Count(int n) { int co...
  • 如何计算整数的位数,并逆序输出? 首先需要对该整数进行分解,获得每一位的数值,将其存放在数组里,然后输出其位数并逆序输出 代码可直接使用,若要求不同,只需进行相应的修改即可 #include&lt;stdio.h&...
  • 如何计算merge()? 在归并过程中,让i作为左边数组的遍历索引,j作为右边数组的遍历索引。在合并的过程中,如果a[i]>b[j],那么合并之后就会产生mid-i个逆序数对。因为a[i+1],a[i+2],...,a[mid...
  • 题目11:有1、2、3、4个数字,能组成多少个互不相同且无重复数字的三位?都是多少? 分析:如何有两位出现相同,变量加加 public class NoRepeatNumber { public static void main(String[] args) { //...
  • (给ImportNew加星标,提高Java技能)编译:ImportNew/覃佑桦www.baeldung.com/java-stream-integers-median-using-heap1.概述本文介绍了如何查找整数流的中位。我会通过示例说明问题,分析问题,最后给出几种Java...
  • 2.逆序打印出各位数字;3.正序打印出各位数字。 前提说明: 从题中我们可以看出题目中对整数的位数已经限制为5位,我们在这里先不管这个限制,无论输入什么数字都将其按照后面的问题输出 1.求它是几位? 我们...
  •   人生伟业的建立,不在能知...文章目录如何计算用户输入的是几位?如何逆序输出数值?思路1:循环了几次?思路2:循环什么时候终止?判断回文写在后面 如何计算用户输入的是几位?   在做逆序输出以及
  • 1.2 如何实现链表的逆序 【华为笔试题】 难度系数:⭐⭐⭐ 考察频率:⭐⭐⭐⭐ 题目描述: 给定两个单链表, 链表的每个结点代表一位计算两个的和。例如:输入链表(3 -> 1 -> 5)和链表(5 -> 9 -&...
  • 如何实现反序

    2020-04-08 21:06:43
    第一次记录自己的学习过程,从简单的开始,一步步的来!...但是如此计算需要设置多个变量来接收得到的各个数位上的值,所以我想是不是有更简单的办法来实现逆序数,先不多说,上代码 #include&...
  • 既然我们之前已经学了不少倒序的方法了,今天我们就进入实战,看看在数组中的逆序如何输出的吧。将一个数组逆序输出,用第一个与最后一个交换。#!/usr/bin/python# -*- coding: UTF-8 -*-i...
  • C语言 整数的逆序

    2019-04-30 09:12:00
    一个整数是由1至多位数字组成的,如何分解出整数的各个位上的数字,然后加以计算 对一个整数做%10的操作,就得到它的个位数; 对一个整数做/10的操作,就去掉了它的个位数; 然后再对上结果做%10,就得到原来的十...
  • 新的想法求逆序

    2019-07-28 14:26:53
    在排好序的序列中找打比k1k_{1}k1​小于等于的,然后该数字后面的数字个就是数字k1k_{1}k1​的逆序对个。 关于排序是用优先队列 关于如何找到小于等于k1k_{1}k1​的,可以用二分查找 粗略计算时间复杂度O...
  • 既然我们之前已经学了不少倒序的方法了,今天我们就进入实战,看看在数组中的逆序如何输出的吧。 将一个数组逆序输出,用第一个与最后一个交换。 #!/usr/bin/python # -*- coding: UTF-8 -*- if __name__ == '__...
  • 题解:用字符数组存两个因数,再将数组逆序以便处理,再对每一个位进行处理,注意字符类型与整型的变换,每一位相乘时需将每位上的字符减48,最后存计算结果时载加48,输出是需逆序输出。 代码如下: #include ...
  • 和归并排序一样,划分和递归求解都好理解,关键在于合并:如何求出i在左边,而j在 右边的逆序对数目呢?统计的常见技巧是“分类”。下面按照j的不同把这些“跨越两边”的逆序 对进行分类:只要对于右边的每个j,...
  • 两种解法,第一种是在原有的两个链表中选择更长的那个作为结果返回,虽然节约了空间,但是增加了时间复杂度,而且没有用到如何设置链表的增加与删除,第二种看起来清爽很多,逻辑也清晰。### 题目给出两个非空的链表...
  • 给出一列a1,a2,a3....an,求它们的逆序对数,即有多少个有序对(i,j) 使得i,ai>aj,n高达10的6次方 思路: 和归并排序一样,划分和递归求解都好办,关键在于合并;如何求出i在左边 而j在右边的逆序对数呢?统计的常见...
  • 这题(BZOJ2431的加强版)厉害了。。。 考虑从小到大加入,则i就可以让逆序对数+[0,i-1] 问题就变为了现在有一个不定方程:x1+..+xn=m,且0 考虑用容斥,于是要计算F(i,j)表示[1,n]选i个和为j的方案...如何计算F
  • 来的顺序再排回来,然后根据每一个的大小对号入座,在入座的过程中我们计算在这个叶子节点的右边有多少个已经 入座的元素,这时候就体现出来了线段树的便捷:查询效率为O(log n) 级别。然后使用s.
  • 【题目描述】 HDU - 5919 Sequence II ...首先,我们分析一个简单一些的问题:对于右端点固定的区间,如何计算不同左区间内不同数字的个数。 我们不妨用一个数组记录cntcntcnt哪些位置出现了一个...
  • 一个排列逆序数的总数称为这个排列的逆序数 如(5,4,2,3,1 )的逆序数为 n = 4+3+1+1= 9 (1,4,2,3,5 )的逆序数为 n = 0+2+0+0= 2 逆序数为奇数称排列为奇排列,逆序数为偶数称排列为偶排列 行列式 这里小...
  • 上一个随笔,我介绍了全排列的递归求解,其中还有排列的逆序数等代码,这次我来介绍如何使用全排列计算行列式的值。使用全排列求行列式的值,简单的描述就是:对这个行列式每一行选取一个数,这些数处于行列式的不同...
  • HDU1282 回文猜想

    2016-05-08 00:35:00
    程序中用了一个小技巧,判断是否为回文数的函数中,反正都要算逆序数,那就作为一个参数变量的返回值利用一下。 不过,根据输出的顺序,还是需要将计算过程暂时存储在数组中,最后再输出。这是无奈的事情。 程序...

空空如也

空空如也

1 2 3 4 5
收藏数 99
精华内容 39
关键字:

如何计算逆序数