精华内容
下载资源
问答
  • 写在前面:由本文开始记录...求逆序对数问题是归并排序的基础问题,显著逆序对数则是逆序对数的升级版。POJ2299,POJ1804均是此类问题(但是个别细节不同,例如POJ2299需要将逆序对数变量num设为long long int型)。
    写在前面:由本文开始记录本人的算法刷题之路,日后会不定期更新,欢迎讨论!本系列系本人原创,如需转载或引用,请注明原作者及文章出处。
    求逆序对数问题是归并排序的基础问题,显著逆序对数则是逆序对数的升级版。POJ2299,POJ1804均是此类问题(但是个别细节不同,例如POJ2299需要将逆序对数变量num设为long long int型)。
    一、求逆序对数
    描述
    对于一个长度为N的整数序列A,满足i < j 且 Ai > Aj的数对(i,j)称为整数序列A的一个逆序。请求出整数序列A的所有逆序对个数
    输入
    输入包含多组测试数据,每组测试数据有两行
    第一行为整数N(1 <= N <= 20000),当输入0时结束
    第二行为N个整数,表示长为N的整数序列
    输出
    每组数据对应一行,输出逆序对的个数
    样例输入51 2 3 4 555 4 3 2 1110样例输出0100解体思路

    归并排序,大家看代码自行理解吧。

    代码

    #include<iostream>
    #include<algorithm>
    using namespace std;
    int n, a[20010], temp[20010], num;
    
    void merge(int begin, int mid, int end)
    {
    	int i = begin;
    	int j = mid + 1;
    	int k = begin;
    
    	while (i <= mid && j <= end)
    	{
    		if (a[i] > a[j])
    		{
    			temp[k] = a[j];
    			k++;
    			j++;
    			num += mid - i + 1;
    		}
    		else
    		{
    			temp[k] = a[i];
    			k++;
    			i++;
    		}
    	}
    
    	while (i <= mid)
    	{
    		temp[k] = a[i];
    		k++;
    		i++;
    	}
    
    	while (j <= end)
    	{
    		temp[k] = a[j];
    		k++;
    		j++;
    	}
    
    	for (int p = begin; p <= end; p++)
    		a[p] = temp[p];
    }
    
    void mergesort(int begin, int end)
    {
    	if (begin >= end)
    		return;
    
    	int mid = (begin + end) / 2;
    	mergesort(begin, mid);
    	mergesort(mid + 1, end);
    	merge(begin, mid, end);
    }
    
    int main()
    {
    	while (1)
    	{
    		cin >> n;
    		if (n == 0)
    			break;
    
    		for (int i = 0; i < n; i++)
    			cin >> a[i];
    
    		num = 0;
    		mergesort(0, n - 1);
    
    		cout << num << endl;
    	}
    	return 0;
    }


    二、求显著逆序对数
    描述
    对于一个长度为N的整数序列A,满足i < j 且 Ai > 2 * Aj的数对(i,j)称为整数序列A的一个显著逆序。请求出整数序列A的所有显著逆序对个数
    输入
    输入包含多组测试数据,每组测试数据有两行
    第一行为整数N(1 <= N <= 20000),当输入0时结束
    第二行为N个整数,表示长为N的整数序列
    输出
    每组数据对应一行,输出显著逆序对的个数
    样例输入51 2 3 4 555 4 3 2 1612 10 8 6 4 20样例输出046
    解体思路
    与求逆序对数不同,由于Ai > 2 * Aj,因此需要将排序和计数分别操作。也就是先做count,再做merge。
    代码
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int n, a[20010], temp[20010], num;
    
    void mcount(int begin, int mid, int end)
    {
    	int i = begin;
    	int j = mid + 1;
    	int k = begin;
    	while (i <= mid && j <= end)
    	{
    		if (a[i] > 2 * a[j])
    		{
    			num += mid - i + 1;
    			j++;
    		}
    		else
    			i++;
    	}
    }
    
    void merge(int begin, int mid, int end)
    {
    	int i = begin;
    	int j = mid + 1;
    	int k = begin;
    
    	while (i <= mid && j <= end)
    	{
    		if (a[i] > a[j])
    		{
    			temp[k] = a[j];
    			k++;
    			j++;
    		}
    		else
    		{
    			temp[k] = a[i];
    			k++;
    			i++;
    		}
    	}
    
    	while (i <= mid)
    	{
    		temp[k] = a[i];
    		k++;
    		i++;
    	}
    
    	while (j <= end)
    	{
    		temp[k] = a[j];
    		k++;
    		j++;
    	}
    
    	for (int p = begin; p <= end; p++)
    		a[p] = temp[p];
    }
    
    void mergesort(int begin, int end)
    {
    	if (begin >= end)
    		return;
    
    	int mid = (begin + end) / 2;
    	mergesort(begin, mid);
    	mergesort(mid + 1, end);
    	mcount(begin, mid, end);
    	merge(begin, mid, end);
    }
    
    int main()
    {
    	while (1)
    	{
    		cin >> n;
    		if (n == 0)
    			break;
    
    		for (int i = 0; i < n; i++)
    			cin >> a[i];
    
    		num = 0;
    		mergesort(0, n - 1);
    
    		cout << num << endl;
    	}
    
    	return 0;
    }



    展开全文
  • 用改进后的分治算法来实现逆序对数问题,使其时间复杂度为 nlogn。 (逆序对数的定义:在数 组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对)。 2. 问题分析 2.1 改进前的方法 把数组...

    1. 问题描述

    用改进后的分治算法来实现逆序对数问题,使其时间复杂度为 nlogn。
    (逆序对数的定义:在数
    组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对)。

    2. 问题分析

    2.1 改进前的方法

    把数组中间分割成子数组,统计出子数组内部逆序对的数目,再统计出两个相邻子数组之间逆序对的数目。按照这种思路,可以写出下列伪代码:
    在这里插入图片描述

    // An highlighted block
    def count _ Inv _ DC _1( A ) :
    	# 统 计 左 边 的 子 数 组 逆 序 对 的 个 数
    	a = count _ Inv _ DC _1( LA )
    	# 统 计 右 边 的 子 数 组 逆 序 对 的 个 数
    	b = count _ Inv _ DC _1( RA )
    	# 统 计 两 个 相 邻 子 数 组 之 间 逆 序 对 的 个 数
    	c = cross ( LA , RA )
    return a + b + c
    

    用传统的逻辑来实现 cross 函数,对左右子数组之间的每一个元素进行比较,需要 O(n^2) 的时间复杂度。那么,
    T(n) = 2T(n / 2) + cn^2
    由 Master Method 可知,该算法的时间复杂度为 O(n2
    ), 说明在这种情况下分治算法也无法提高效率。

    2.2 改进后的方法

    改进思路:在统计逆序对的过程中,对数组进行排序,使 cn2 → cn。
    在这里插入图片描述
    在合并时,每一层的比较次数是 n,一共有 logn 层,由此可得,该排序的时间复杂度是 O(nlogn)。
    在做合并的时候将有序的特征进行传递,因此得到了性能的提升。

    3. 实验代码

    // An highlighted block
    import time
    import random
    import matplotlib . pyplot as plt
    import numpy as np
    from scipy . optimize import curve _ fit
    
    # 自 定 义 函 数 e 指 数 形 式
    def func (x , a , b , c ) :
    	return a * np . sqrt ( x ) *( b * np . square ( x ) + c )
    	
    def random _ list ( length ) :
    	randomlist = []
    	for i in range ( length ) :
    		randomlist . append ( i +1)
    	random . shuffle ( randomlist )
    	return randomlist
    
    def count _ Inv _ DC ( A ) :
    	if len ( A ) <= 1:
    		return A ,0
    	else :
    		mid = len ( A ) //2
    		LA = A [: mid ]
    		RA = A [ mid :]
    		SLA , count 1 = count _ Inv _ DC ( LA ) # 统 计 左 边 的 子 数 组 逆 序 对 的 个 数
    		SRA , count 2 = count _ Inv _ DC ( RA ) # 统 计 右 边 的 子 数 组 逆 序 对 的 个 数
    		SA , count 3 = cross ( SLA , SRA ) # 统 计 两 个 相 邻 子 数 组 之 间 逆 序 对 的 个 数
    	return SA , count 1+ count 2+ count 3
    
    def cross ( LA , RA ) :
    	# 边 排 序 边 计 数
    	result = []
    	i =0
    	j =0
    	count = 0
    	while i < len ( LA ) and j < len ( RA ) :
    		if LA [ i ] < RA [ j ]:
    			result . append ( LA [ i ])
    			i = i + 1
    		else :
    			result . append ( RA [ j ])
    			count = len ( LA ) - i
    			j = j + 1
    	while i < len ( LA ) :
    		result . append ( LA [ i ])
    		i = i + 1
    	while j < len ( RA ) :
    		result . append ( RA [ j ])
    		j = j + 1
    	return result , count
    
    if __ name __ == "__ main __":
    	x = [100 ,1000 ,10000 ,100000 ,1000000]
    	time _ list = []
    	for index in range ( len ( x ) ) :
    		average _ time = []
    		
    	for i in range (10) :
    		# print ( ’ x :, x [ index ])
    		randomlist = random _ list ( x [ index ])
    		# randomlist = random _ int _ list (1 , x [ index ] , x [ index ])
    		total _ time = 0
    		time _ start = time . time ()
    		count _ Inv _ DC ( randomlist )
    		time _ end = time . time ()
    		total _ time = time _ end - time _ start
    		average _ time . append ( total _ time )
    	# 求 平 均 值
    	average = np . mean ( average _ time )
    	time _ list . append ( average )
    print ( time _ list )
    
    # 用 matplotlib 画 图
    # plt . figure ()
    # plt . plot (x , time _ list , marker =*, label = " merge sort ")
    # plt . show ()
    
    # 定 义 x 、 y 散 点 坐 标
    x = np . array ( x )
    num = time _ list
    y = np . array ( num )
    
    # 非 线 性 最 小 二 乘 法 拟 合
    popt , pcov = curve _ fit ( func , x , y )
    # 获 取 popt 里 面 是 拟 合 系 数
    print ( popt )
    a = popt [0]
    b = popt [1]
    c = popt [2]
    yvals = func (x ,a ,b , c ) # 拟 合 y 值
    
    # 绘 图
    plot 1 = plt . plot (x , y , ’s ’ , label = ’ original values ’)
    plot 2 = plt . plot (x , yvals , ’r ’ , label = ’ polyfit values ’)
    plt . xlabel ( ’x ’)
    plt . ylabel ( ’y ’)
    plt . legend ( loc =4) # 指 定 legend 的 位 置 右 下 角
    plt . title ( ’ Inversions ’)
    plt . show ()
    
    # 统 计 100 个 随 机 数 中 逆 序 对 的 个 数
    AList = random _ list (100)
    countNum = count _ Inv _ DC ( randomlist )
    print ("100 个 随 机 数 中 逆 序 对 数 的 个 数 为 : " , countNum [1])
    

    4. 实验结果

    4.1 时间复杂度结论

    计算不同范围大小下的随机数组中寻找逆序对数的个数所要消耗的时间,在多次实验求平均值,并对图像进行拟合处理后,得到上述图像。可以看到,该方法求解逆序对数问题的时间复杂度图像近似于 nlogn,这与我们理论验证的结果相同。
    在这里插入图片描述

    4.2 逆序对个数结论

    随机生成 100 个数,实验得在该数组中存在 86 个逆序对。
    在这里插入图片描述

    参考和致谢

    【1】逆序对数问题https://blog.csdn.net/contr4l_/article/details/80611675

    展开全文
  • 分治求逆序对数 问题描述 在Internet上的搜索引擎经常需要对信息进行比较,比如可以通过某个人对一些事物的排名来估计他对各种不同信息的兴趣,从而实现个性化服务。对于不同的排名结果可以用逆序来评价他们之间的...

    分治求逆序对数

    问题描述

    在Internet上的搜索引擎经常需要对信息进行比较,比如可以通过某个人对一些事物的排名来估计他对各种不同信息的兴趣,从而实现个性化服务。对于不同的排名结果可以用逆序来评价他们之间的差异。考虑1,2,……,n的排列i1,i2,……in,如果其中存在ij,ik使得j<k但是i1>ik,那么就称ij,ik是这个排列的一个逆序。一个排列含有逆序的个数称为这个排列的逆序数。设计和实现统计逆序的分治算法,并对算法进行时间复杂度分析。

    解决思路

    寻找数组中的逆序对数,暴力的做法就是两层遍历,比较每两组数的大小,但暴力做法的时间复杂度达到了O(n^2),这显然是难以让人接受的。逆序对的定义是在一对数满足ij>ik并且j<k,这样的数对我们应该很熟悉,在任何一个待排数组中很容易见到,那么我们可不可以借鉴排序的方式求出逆序数呢?在归并排序中,我们需要将两个有序数组合并成一个有序数组,那么对于两个有序数组来说,他们各自的逆序数应当为0,那么我们就只需要考虑两个部分组成的逆序数。例如对于两个有序数组a1 = {0,4,6,8,9,10},a2 = {2,3,6,7} ,我们可以仿照归并排序同时对两个数组进行遍历,如果a1[i] <= a2[j],那么就把a1[i]插入到新的有序数组后,如果a1[i] > a2[j],那么a1[i]就能与a2[j]组成逆序对,又因为两个数组都是有序的,a1[i]后面的数都大于等于a1[i],所以a1中剩下的数都能与a2[j]组成逆序对,因此逆序数需要加上a1.length-i,并将a2[j]插入到新的有序数组后,当两个数组都扫描完时,将得到的新数组赋给原数组即可。我们可以用递归的方式求出整个数组的逆序对数。

    算法代码

    int merge(int a[], int start, int mid, int end)  
    {  
    	int count = 0;  
    	int i = start, j = mid + 1;  
    	int *temp = new int[end - start + 1];//用于存储排序后的元素  
    	int k = 0;  
    	while (i <= mid && j <= end)//归并  
    	{  
    		if (a[i] > a[j])//若左边元素大于右边元素,则存在逆序对,左边剩余元素可以和右边元素组成逆序对  
    		{  
    			temp[k++] = a[j++];  
    			count += mid - i + 1;  
    		}  
    		else  
    			temp[k++] = a[i++];  
    	}  
    	while (i <= mid)temp[k++] = a[i++];//合并剩余元素  
    	while (j <= end)temp[k++] = a[j++];  
    	for (int i = start,j = 0; i <= end; i++,j++)a[i] = temp[j];//将排序后的数组赋给原数组  
    	delete[] temp;  
    	return count;  
    }  
      
    int inversion_pairs(int a[], int start, int end)  
    {  
    	if (start == end)return 0;  
    	int count = 0;  
    	int mid = (start + end) / 2;  
    	count += inversion_pairs(a, start, mid);//左半部分的逆序数  
    	count += inversion_pairs(a, mid + 1, end);//右半部分的逆序数  
    	count += merge(a, start, mid, end);//跨界的逆序数  
    	return count;  
    } 
    

    算法分析

    本算法借鉴了归并算法的思想,仅在归并排序的过程中加入计算逆序数的语句,因此它的时间复杂度与归并排序一致,为O(nlogn),我用相同的数据将暴力算法与归并算法进行了比较,结果如下:

    数据规模归并算法暴力算法
    10001ms5ms
    50004ms66ms
    100008ms263ms
    5000031ms6495ms
    展开全文
  • 今天来学习归并算法的一个应用,求数组中的逆序对数。 首先我们需要知道逆序对是什么东西:在一个数组中,有两个元素,索引小的元素比索引大的元素大,那这两个元素就构成一个逆序对。而一个数组中所有逆序对的个数...

    今天来学习归并算法的一个应用,求数组中的逆序对数。

    首先我们需要知道逆序对是什么东西:在一个数组中,有两个元素,索引小的元素比索引大的元素大,那这两个元素就构成一个逆序对。而一个数组中所有逆序对的个数就叫做逆序对数

    暴力求解法

    我们可以很容易地想出暴力求解的方法:遍历数组,依次取数组中的每一个数,然后与索引排在其后的元素比较,如果比它小,则逆序对数+1,遍历完毕,得到的逆序对数则是数组的逆序对数。

    代码如下:

    /**
     * 暴力求解法求逆序对数
     * @param nums 数组
     * @return 逆序对数
     */
    public static int inversionPairCountBruteForce(int[] nums) {
        Objects.requireNonNull(nums);
        if (nums.length <= 1) {
            // 数组最多只有一个元素,无法构成逆序对
            return 0;
        }
        int inversionPairCount = 0;
        // 遍历数组
        for (int i = 0; i < nums.length - 1; i++) {
            // 遍历该元素后续元素,查找逆序对
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] > nums[j]) {
                    // 找到则逆序对数+1
                    System.out.println("[" + nums[i] + ", " + nums[j] +  "]");
                    inversionPairCount++;
                }
            }
        }
        return inversionPairCount;
    }
    

    暴力求解法的算法复杂度为O(n2),那么我们有没有更优的解法了呢?

    学点算法(三)——数组归并排序里面我们提到了分而治之的思想,在求逆序对的问题上,是否也可以用此思想呢?

    归并算法求数组逆序对数

    答案是可以的。我们一步步来分析:

    1. 要求一个数组的所有逆序对数,可以先将它分为两部分,左子数组和右子数组。
    2. 分割完毕后,一个数组的总逆序对数 = 左子数组的总逆序对数 + 右子数组的总逆序对数 + 左子数组和右子数组中交叉的逆序对数。
    3. 要求左(右)子数组的逆序对数我们可以使用递归的方法继续求,而左子数组和右子数组中交叉的逆序对数这个该怎么求呢?如果不施加任何条件,我们还是需要遍历左子数组中的元素,然后依次取右子数组中的元素进行对比,这样比较下来我们还是需要O(n2)的算法复杂度。
    4. 而我们知道如果经过归并排序后,左子数组和右子数组会分别变为有序的,那么我们在对比一组元素之后,如果发现逆序(左子数组中的元素比右子数组的元素大),那么右子数组的该元素会与左子树中后续所有元素构成逆序对。通过这个发现,我们可以利用归并排序算法代码,来求逆序对数,而该算法复杂度也优化到了和归并排序一致,为O(nlogn)。

    我们取[53, 89][32, 45, 67]的归并来说明这个过程:

    1. 左子数组的53和右子数组的32对比,发现53大于32,那么32将和左子数组中53及其以后的元素构成逆序对,即[53, 32][89, 32]在这里插入图片描述
    2. 左子数组的53和右子数组的45对比,发现53大于45,那么45将和左子数组中53及其以后的元素构成逆序对,即[53, 45][89, 45]在这里插入图片描述
    3. 左子数组的53和右子数组的67对比,发现53小于45,则无逆序对。
      在这里插入图片描述
    4. 左子数组的89和右子数组的67对比,发现89大于67,那么67将和左子数组中89及其以后的元素构成逆序对,即[89, 67]
      在这里插入图片描述
    5. 右子数组中已无元素,则后续无逆序对。
      在这里插入图片描述
      累加每一次对比的结果:2 + 2 + 1可以得到交叉的逆序对数为5

    我们只需要在归并排序算法(归并排序算法请见学点算法(三)——数组归并排序)的基础上稍作修改即可得到求逆序数的算法:

    /**
     * 数组的归并排序算法(同时求逆序对数)
     *
     * @param nums 数组
     * @param lo 区间的lo索引(包含)
     * @param hi 区间的hi索引(不包含)
     */
    public static int inversionPairCountMergeSort(int[] nums, int lo, int hi) {
        // 数组为null则直接返回
        if (nums == null) {
            return 0;
        }
        // 索引检查
        if (lo < 0 || nums.length <= lo) {
            throw new IllegalArgumentException("lo索引必须大于0并且小于数组长度,数组长度:" + nums.length);
        }
        if (hi < 0 || nums.length < hi) {
            throw new IllegalArgumentException("hi索引必须大于0并且小于等于数组长度,数组长度:" + nums.length);
        }
        if (hi <= lo) {
            // lo索引必须小于hi索引(等于也不行,因为区间是左闭右开,如果等于,区间内元素数量就为0了)
            throw new IllegalArgumentException("lo索引必须小于hi索引");
        }
        if (lo + 1 >= hi) {
            // 区间元素个数最多为1
            // 无需排序,逆序数为0
            return 0;
        }
        int inversionPairCount = 0;
        int mid = (lo + hi) / 2;
        // 对左子区间排序,并加上逆序对数
        inversionPairCount += inversionPairCountMergeSort(nums, lo, mid);
        // 对右子区间排序,并加上逆序对数
        inversionPairCount += inversionPairCountMergeSort(nums, mid, hi);
        // 对两个排序好的子区间归并,得到一个整体有序的区间,并加上两个子区间交叉的逆序对数
        inversionPairCount += merge(nums, lo, mid, hi);
        return inversionPairCount;
    }
    
    public static int merge(int[] nums, int lo, int mid, int hi) {
        // 这里不用检查索引,调用方已经决定了索引是有效的
        // 结果区间和右子区间使用原有数组
        // 左子区间使用临时数组(因为结果区间可能会覆盖左子区间的元素,所以需要开辟新数组保存)
        int inversionPairCount = 0;
        int leftLen = mid - lo;
        int[] left = new int[leftLen];
        System.arraycopy(nums, lo, left, 0, leftLen);
        // 左子区间索引
        int leftIdx = 0;
        // 右子区间索引
        int rightIdx = mid;
        // 结果区间索引
        int resultIdx = lo;
        while (true) {
            if (leftIdx < leftLen && rightIdx < hi) {
                // 两个子区间都存在元素
                // 取两个子区间的有效首元素对比
                if (left[leftIdx] <= nums[rightIdx]) {
                    // 左子区间首元素小于右子区间首元素
                    // 将左子区间首元素放到结果位置,同时更新索引位置
                    nums[resultIdx++] = left[leftIdx++];
                } else {
                    // 右子区间首元素小于左子区间首元素
                    // 将右子区间首元素放到结果位置,同时更新索引位置
                    nums[resultIdx++] = nums[rightIdx++];
                    for (int i = leftIdx; i < leftLen; i++) {
                        System.out.println("["  + left[i] + ", " + nums[rightIdx-1] + "]");
                    }
                    inversionPairCount += (leftLen - leftIdx);
                }
            } else {
                if (leftIdx < leftLen) {
                    // 左子区间还有剩余元素
                    // 直接将左区间所有元素一起移动到结果位置
                    System.arraycopy(left, leftIdx, nums, resultIdx, leftLen - leftIdx);
                } else {
                    // 右子区间还有剩余元素
                    // 因为经过上一次判断,左子区间和右子区间只会有一个存在剩余元素
                    // 直接将右区间所有元素一起移动到结果位置
                    System.arraycopy(nums, rightIdx, nums, resultIdx, hi - rightIdx);
                }
                // 全部元素移动完毕,退出
                break;
            }
        }
        return inversionPairCount;
    }
    

    测试代码如下:

    int[] nums = {2, 343, 4, 1, 3, 5, 7};
    System.out.println(inversionPairCountBruteForce(nums));
    System.out.println(inversionPairCountMergeSort(nums, 0, nums.length));
    

    输出如下:

    [2, 1]
    [343, 4]
    [343, 1]
    [343, 3]
    [343, 5]
    [343, 7]
    [4, 1]
    [4, 3]
    暴力求解法求逆序对数:8
    [343, 4]
    [2, 1]
    [4, 1]
    [343, 1]
    [4, 3]
    [343, 3]
    [343, 5]
    [343, 7]
    归并排序法求逆序对数:8
    

    符合我们的预期。

    展开全文
  • 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列(即先使每个子序列有序,再使子序列段...
  • 最长非降子序列以及逆序对数1.最长非降子序列2.逆序对数 1.最长非降子序列 时间复杂度:O(nlogn) 代码: public class 最长非降子序列 { public static void main(String[] args) { int []arr={1,2,5,4,6,4,5...
  • 算法设计课上老师给出了如上一个问题,让用刚学习的归并排序算法来实现求逆序对数。 那么我们很容易想到这个题有一种O(n*n)的暴力解法,但这不是我们所需要的,所以,要想归并排序来实现求逆序对数,那么首先...
  • 算法设计第三次上机作业-求逆序对数 题目描述 对于一个长度为N的整数序列A,满足i < j 且 Ai > Aj.的数对(i,j)称为整数序列A的一个逆序 请求出整数序列A的所有逆序对个数 输入 输入包含多组测试数据,每组测试...
  • 分治算法之求逆序对数

    千次阅读 2016-10-18 20:04:49
    如果用分治方法求出逆序对数,这就类似与归并排序算法。先将数组从中间分成两个部分,然后分别递归左半部分和右半部分,再合并排好序的左右两个部分,从而统计逆序对数。比如合并两个排好序的数组{1,4,5,7}和{2,3},...
  • 思路:这题最主要的就是求每个数字的到当前状态时的逆序对数(修改前和后),之前想的是用multiset存储数字,用upper_bound求比当前值大的数,用distance去计算逆序对的个数,但是后来发现distance在这种不可随机...
  • 逆序对数: 给出一列数a1,a2,...,an,求它的逆序对数,即有多少个有序对(i,j),使得iaj。n可以高达10^6 思路: 分解成前后两个序列,统计后序列中每个元素与前面中每个元素的逆序对数,是一个叉乘 书析: 采用O(n^2)...
  • 算法】求一个数组中的逆序对数

    千次阅读 2017-09-06 11:51:28
    题目描述 在数组中的两个数字,如果前面一个数字...最简单的解法就是遍历数组中的每一个元素,让每个元素与后面的元素对比,如果大于则逆序对数count++,但是时间复杂度是o(n2) 比较好的思路是利用分治的思想:
  • 逆序对数

    2011-11-22 19:49:23
    这个算法与归并排序相似  int cnt = 0;//对数个数, void re(int *b,int x,int y,int *t){  if(y-x>1){//递归退出条件  int m = x+(y-x)/2;  int p = x,q=m,i=x;  re(b,x,m,t);  re(b,m,y,t);  while...
  • 给定有序表A[1:n] 修改合并排序算法,求出该有序表的逆序对数 有关逆序对数的概念: 定义:对于一个给定的数列,如果有i<j,且Ai>Aj,则称(i,j)为一逆序对. 要解决的问题是,给出一个数列,求出这个数列包含多少个...
  • 今天做《算法导论》习题,求解逆序对,更改分治排序法,写出求解逆序对的算法。时间复杂度为nlgn /************************************************************ * count_inverse.c * * To count the inverse ...
  • 当我们删除a时,减少的是 与a有关的逆序对数,当我们把a的位置填充b时增加的是 与b有关的逆序对数,可以用树状数组求 这样我们相处了nmlogK的算法,显然是不能承受的(K=500000) 但是我们发现当a相同时我们可以将...
  • 2、逆序对数问题 另外再补充一个 LintCode532Reverse Pairs归并排序求解逆序数 的问题: 这个的关键在于, 在合并 l ~ mid 和 mid+1~r 的过程中,只要 arr[p1] > arr[p2] ,则 arr[p2] 和 arr[p1 ~ ...
  • 总时间限制:  ...请求出整数序列A的所有逆序对个数 输入 输入包含多组测试数据,每组测试数据有两行 第一行为整数N(1 &lt;= N &lt;= 20000),当输入0时结束 第二行为N个整数,表示长为N的整数...
  • "逆序对数为%lld\n" , ans ) ; return 0 ; } 思路解析: 在分治的同时,加入判断 对于L数组和R数组,应该是L数组排在R数组前, 所以如果R数组的首元素比L数组的首元素小, 那么R数组首元素比L[i]到L...

空空如也

空空如也

1 2 3 4 5 ... 17
收藏数 323
精华内容 129
关键字:

逆序对数算法