精华内容
下载资源
问答
  • 题意:两个排好序的数组合并后的中位数。 解题思路担心直接sort会超时,所以拿归并排序的merge方法合并数组,即从每次都从两个数组剩余的元素中挑出最小的,若某个数组先挑完,则另一个数组原样抄回。然而,sort...

    题目

    https://www.patest.cn/contests/pat-a-practise/1029

    题意:求两个排好序的数组合并后的中位数。

    解题思路

    担心直接sort会超时,所以拿归并排序的merge方法合并数组,即从每次都从两个数组剩余的元素中挑出最小的,若某个数组先挑完,则另一个数组原样抄回。

    然而,sort也能过……(摊手)

    顺便复习一下归并排序:

    归并排序利用了分治的思想,将数列a[l,h]分成两半a[l,mid]和a[mid+1,h],分别进行归并排序,然后再将这两半合(merge)并起来。

    利用归并排序可以求逆序对的数目。即在合并的过程中(设l<=i<=mid,mid+1<=j<=h),当a[i]<=a[j]时,并不产生逆序数;当a[i]>a[j]时,在前半部分中比a[i]大的数都比a[j]大,将a[j]放在a[i]前面时,逆序数要加上mid+1-i。因此,可以在归并排序中的合并过程中计算逆序数。

    AC代码

    #include <iostream>
    using namespace std;
    
    const int maxn = 1000005;
    long int a[maxn], b[maxn], res[maxn<<1];
    int lena, lenb, cnt;
    
    int main()
    {
        ios::sync_with_stdio(false);
        cin >> lena;
        for (int i = 0; i < lena; ++i)
            cin >> a[i];
        cin >> lenb;
        for (int i = 0; i < lenb; ++i)
            cin >> b[i];
        //归并排序的merge步骤
        int p1 = 0, p2 = 0, cnt = 0;
        while (p1 < lena && p2 < lenb)
        {
            if (a[p1] < b[p2]) 
            {
                res[cnt++] = a[p1];
                p1++;
            }
            else
            {
                res[cnt++] = b[p2];
                p2++;
            }
        }
        if (p1 < lena) //p1还有剩余
        {
            for (int i = p1; i < lena; ++i)
                res[cnt++] = a[i];
        }
        if (p2 < lenb) //p2还有剩余
        {
            for (int i = p2; i < lenb; ++i)
                res[cnt++] = b[i];
        }
        cout << res[(cnt-1)>>1] << endl; //输出中位数
        return 0;
    }
    
    展开全文
  • 归并排序求逆序对 题目大意 给你多个序列,让你求出每个序列逆序对的数量。 输入:每组数据以一个 n 开头,以下n行,每行一个数字,代表这个序列; 输出:对于输出对应该组数据的逆序对的数量; 顺便在此吐...

    归并排序求逆序对

    题目大意

    给你多个序列,让你求出每个序列中逆序对的数量。

    输入:每组数据以一个数 n 开头,以下n行,每行一个数字,代表这个序列;

    输出:对于输出对应该组数据的逆序对的数量;

    顺便在此吐槽一下翻译器,翻译了一顿我啥都看不懂(都怀疑自己是不是中国人了),幸亏自己还能看懂点英语啊。

    这个题是机房里一位小伙伴问我我才做的,蒟蒻的我刚开始居然想要双重循环(类似于冒泡排序的方法)来做,看完数据范围之后就放弃了;

            然后想到了逆序对是使用归并排序来做的,所以就自己手码了一个归并排序;;可能有的小伙伴还不知道归并排序的思想,所以看了一晚上归并排序的蒟蒻——我,就来给小伙伴们介绍一下吧!

    归并排序:

    nlog(n)的稳定算法(可用于求逆序对的个数)

    应用方法:

    二分(所以又叫二路归并)+递归;

    为什么使用递归?   

    answer:要使用归并排序首先就要将数据分解,一直分解到每一个单位,然后就是进行合并了;

    如何合并? 

    answer:比较a[i]和a[j]的大小(其中a[i]属于左区间,a[j]属于右区间,其实就是将左右区间合并、并排序),若a[i]<a[j],则将a[i]复制到r[k]中,然后将r和k都加1,否则将a[j]复制到r[k]中,将r,k加1,最后再将r[k]移动到a[i]中,然后继续合并;

    如何求逆序对? 

    answer:

    下面就是 归并排序求逆序对 的过程==

     1 #include<cstdio>
     2 using namespace std;
     3 const int maxn=5e5+5;
     4 int a[maxn],r[maxn],n;//r[]是辅助用的; 
     5 long long ans;//ans作为全局变量记录每次逆序对的数量;
     6 //记得ans要开long long,否则WAWAWA
     7 void msort(int s,int t){
     8     if(s==t) return;
     9     int mid=(s+t)>>1;//二进制下右移一位,相当于 /2 ,但是速度更快! 
    10     msort(s,mid),msort(mid+1,t);//递归的体现 
    11     int i=s,j=mid+1,k=s;
    12     while(i<=mid&&j<=t)
    13         if(a[i]<=a[j]) r[k]=a[i],i++,k++;
    14         else r[k]=a[j],j++,k++,ans+=mid-i+1;
    15         //ans的计算是最神奇的地方,不过动动脑子,画个图啥的也是可以想出来的 
    16     while(i<=mid) r[k]=a[i],i++,k++;
    17     while(j<=t) r[k]=a[j],j++,k++;
    18     for(int i=s;i<=t;i++) a[i]=r[i];//每次要更新的是 a[]数组!! 
    19 }
    20 int main(){
    21     while(1){//来一个无限的循环== 
    22         scanf("%d",&n);
    23         if(!n) return 0;//(!n相当于n==0,当然速度也是快一点的啦!)n=0就直接结束程序; 
    24         for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    25         msort(1,n);        
    26         printf("%lld\n",ans);
    27         ans=0;//注意:ans每次都需要清0; 
    28     }
    29 }
    poj2299

    --------------------------------------------------下方高能--------------------------------------------

    其实只是一个实例,解释一下ans是如何求出来的啦

     

            a[i]         mid=4    a[j]

           3 4 7 9                         1 5 8 10

    首先将右区间的 1 取出,放到r[k]中,此时 1 是比每个a[i]中的元素都小,也就是说此时i的指针指向 a[1] 的位置,此刻得到的逆序对的数量为 4 ; r[k]= 1 ;

    然后再将a[i]a[j]比较(直到a[i]<a[j]),a[i]<a[j]  a[i]的元素放到r[k]中;  r[k]= 1 3 4;现在a[j]>a[i], i 指向 a[3] 的位置,将5 放到 r[k] 中,得到的逆序对数量为 2 ; r[k]= 1 3 4 5

     以此类推,直到进行完归并排序,每次合并都会求出逆序对的数目,即 mid-i+1 ,最后每次将 ans 加上 mid-i+1即可得到最后的答案;

     

     

    其实求逆序对呢,还可以用线段树,不过对于如此蒟的蒟蒻我,还是算了吧,有兴趣的小伙伴也可以自己从网上搜着看一下,蒟蒻在此就不介绍给大家了(我也不会啊)

     

    转载于:https://www.cnblogs.com/RisingGods/p/8271098.html

    展开全文
  • 例如,若序列S1=(11, 13, 15, 17, 19),则S1的中位数是15,两个序列的中位数是含它们所有元素的升序序列的中位数。例如,若S2= (2, 4,6,8, 20),则S1和S2的中位数是11。现在有两个等长升序序列A和B,试设计一个在...

    题目:一个长度为L (L>=1)的升序序列S,处在第[L/2]个位置的数称为S的中位数。例如,若序列S1=(11, 13, 15, 17, 19),则S1的中位数是15,两个序列的中位数是含它们所有元素的升序序列的中位数。例如,若S2= (2, 4,6,8, 20),则S1和S2的中位数是11。现在有两个等长升序序列A和B,试设计一个在时间和空间两方面都尽可能高效的算法,找出两个序列A和B的中位数。要求:

    1. 给出算法的基本设计思想。
    2. 根据设计思想,釆用C或C++或Java语言描述算法,关键之处给出注释。
    3. 说明你所设计算法的时间复杂度和空间复杂度。

    该题为2011年研究生考试计算机联考真题。

    第一种方法

    算法思想:1.先将两个升序序列归并排序成一个升序序列,找中位数(最先想到且简单)
    时间复杂度:O(n),空间复杂度:O(n)

    #include"head.h"
    bool findmid1(SeqList A, SeqList B, SeqList& C) {
    	if (A.length + B.length > C.Maxsize) {
    		//return false;//若两表长度之和大于新表最大长度,则返回。
    		//为了更有效的执行算法,此处我们不这样写,如果两表长度之和大于新表最大长度,则新表动态增加空间
    		IncreaseSize(C, 10);//C表自动增加10个长度
    	}
    	int i = 0, j = 0, k = 0;
    	while (i < A.length && j < B.length)
    	{
    		if (A.data[i] < B.data[j])
    		{
    			C.data[k++] = A.data[i++];
    		}
    		else
    		{
    			C.data[k++] = B.data[j++];
    		}
    	}
    	while (i < A.length)
    	{
    		C.data[k++] = A.data[i++];
    	}
    	while (j < B.length)
    	{
    		C.data[k++] = B.data[j++];
    	}
    	C.length = k;
    	int mid = C.length / 2;
    	printf("C表中位数为:%d\n", C.data[mid-1]);//中位数,数组长度一般下标-1
    	return true;
    }
    

    第二种方法

    算法思想:类比归并排序的思想但并不实现归并,仅按顺序进行访问
    时间复杂度:O(n),空间复杂度:O(1)

    int findmid2 ( int* a, int* b, int len ) {
    	int i = 0, j = 0, k = 0;
    
    	for ( ; k < len-1; k++ ) {
    		if ( a[i] < b[j] ) {
    			i++;
    		}
    		else {
    			j++;
    		}
    	}
    
    	return (a[i] < b[j])? a[i]: b[j];
    }
    //就是从头到尾一共数 len 个数,这个时候两个指针指向的数字较小者即为所求。
    

    第三种方法

    **王道考研参考书中给出的该题的最优方法

    时间复杂度:O(log2n),空间复杂度:O(1)

    分别求两个升序序列A、B的中位数,设为a和b, 求序列A、B的中位数过程如下:

    1. 若a = b,则a或b即为所求中位数,算法结束。

    2. 若a < b,则舍弃序列A中较小的一半,同时舍弃序列B中较大的一半,要求两次舍弃的长度相等。

    3. 若a > b,则舍弃序列A中较大的一半,同时舍弃序列B中较小的一半,要求两次舍弃的长度相等。**

    int findmid3(int A[], int B[], int n)
    {
    	int start1 = 0, end1 = n - 1, m1, start2 = 0, end2 = n - 1, m2;
    	//分别表示序列A和B的首位数、末位数和中位数
    
    	while (start1 != end1 || start2 != end2)
    	{
    		m1 = (start1 + end1) / 2;
    		m2 = (start2 + end2) / 2;
    		if (A[m1] == B[m2])
    			return A[m1];   //满足条件 1)
    
    		if (A[m1] < B[m2]) // 满足条件 2)
    		{
    			if ((start1 + end1) % 2 == 0)  //若元素个数为奇数
    			{
    				start1 = m1;  //舍弃A中间点以前的部分且保留中间点
    				end2 = m2;  //舍弃B中间点以后的部分且保留中间点
    			}
    			else				//元素个数为偶数
    			{
    				start1 = m1 + 1;  //舍弃A中间点及中间点以前部分
    				end2 = m2;  //舍弃B中间点以后部分且保留中间点
    			}
    		}
    		else
    		{  //满足条件3)
    			if ((start2 + end2) % 2 == 0)   //若元素个数为奇数
    			{
    				end1 = m1;    //舍弃A中间点以后的部分且保留中间点
    				start2 = m2;    //舍弃B中间点以前的部分且保留中间点
    			}
    			else     //元素个数为偶数
    			{
    				end1 = m1;    //舍弃A中间点以后部分且保留中间点
    				start2 = m2 + 1;    //舍弃B中间点及中间点以前部分
    			}
    		}
    	}
    	return  A[start1] < B[start2] ? A[start1] : B[start2];
    }
    

    总结

    1. 当在练习的时候可以对三种方法慢慢调试,仔细理解。

    2. 若无法理解第三种最优解的方法建议就不要再看了,考试时第三种方法为满分答案,第二种方法减1分,第一种方法减2分。

    3. 小编在写第一种和第二种方法时一共用了10分钟,第三种方法依然没有理解并成功运行,给诸位大佬程序员丢人了…

    展开全文
  • 以前没有学过归并排序,所以这次研究逆序对很是困难。 感谢这大神,让我终于AC 了逆序对:http://blog.csdn.net/shen823797837/article/details/8794919 其实它的思想与归并排序是一样的,并且是基于归并排序的...

    以前没有学过归并排序,所以这次研究逆序对很是困难。

    感谢这位大神,让我终于AC 了逆序对:http://blog.csdn.net/shen823797837/article/details/8794919

    其实它的思想与归并排序是一样的,并且是基于归并排序的。

    先求各个部分(分治)的逆序对个数,并将该部分的原数组排序。在归并的时候比较两个部分中数的大小,这里排序就派上用场了

    #include <iostream>
    #include <string>
    using namespace std;
    
    int msort(int a[], int px[], int l, int r)//注意px和a数组是在递归过程中不断互换的,因为在递归过程中会进行排序
    {
      if (l == r)
        return 0;
      int mid = l + (r - l) / 2;
      
      int left = msort(px, a, l, mid);
      
      int right = msort(px, a, mid + 1, r);
      
      int i = mid, j = r, k = r + 1;
      
      int ans = left + right;
      while (i >= l && j >= mid+1)
      {
        if (px[i] > px[j])
        {
          a[--k] = px[i--];
          ans += j - mid;
        }
        else
          a[--k] = px[j--];
      }
      while (i >= l)
          a[--k] = px[i--];
      while (j >= mid + 1)
          a[--k] = px[j--];
      return ans;
    }
    int zhongzhuan(int a[], int n)
    {
      int px[110];
      for (int i = 0; i < n; ++i)
        px[i] = a[i];
      return msort(a, px, 0, n-1);
    }
    
    int main() {
      int a[10] = {7, 5, 6, 4};
      cout << zhongzhuan(a, 4) << endl;
      return 0;
    }
    


    展开全文
  • 归并排序,合并有序列表,逆序对个 之所以将标题三者放一起是因为它们有密不可分的关系. 合并有序列表 定义一个空列表 li 用来存放排序后的值; 定义两个 cursor lc 和 rc,分别指向左右列表的首部; 比较 lc 和 ...
  • 请找出两个排序数组的中位数并且总的运行时间复杂度为 O(log (m+n)) 。 示例1: nums1 = [1, 3] nums2 = [2] 中位数是 2.0 复制代码示例2: nums1 = [1, 2] nums2 = [3, 4] 中位数是 (2 + 3)/2 = 2.5 复制代码 归并...
  • ar1[]和ar2[]的中位数 可以借鉴归并排序的思想 实质上就是将将两个已经排好序的数组 合并成一个数组 的过程只是在这个过程中添加了一个计算从小到大的次序的数 (count ) 当count =n 和n+1时记录下这两个数 然后...
  • 归并排序,合并有序列表,逆序对个 之所以将标题三者放一起是因为它们有密不可分的关系. 合并有序列表 定义一个空列表 li 用来存放排序后的值; 定义两个 cursor lc 和 rc,分别指向左右列表的首部; 比较 lc 和 ...
  • 海量数据求中位数

    2020-05-20 00:09:59
    1.利用外排序的方法,进行排序 ,然后再去找中位数注释:外部排序基本上由两个相对独立的阶段组成。首先,按可用内存大小,将外存上含n个记录的文件分成若干长度为h的子文件,依次读入内存并利用有效的内部排序方法对...
  • 两个有序数组求中位数问题; 这个题有很多方法: 方法一:排序,找到中位数; 方法二:归并排序的思想 方法三:转换成求第k小值 */ /* 思路:使用二分查找,时间复杂度为log(m+n). 该方法的核心是将原...
  • 题目大意:已知两个排好序的数组nums1和nums2,长度分别为m和n,要求的是合并nums1和nums2之后的所有数的中位数。时间复杂度要求O(log(m+n))题目分析:容易想到的是归并排序算法,用两个指针分别指向nums1和nums2,...
  • 海量整数,求中位数

    2013-07-05 10:13:05
    遍历一遍,统计总的数目为n,于是定义中位数为n/2 -1, 或者n/2。 将数据读入m个小文件,分别排序,然后仿照归并排序,建立size为m的最小堆,记录堆中每个元素对应的有序文件编号,踢出堆顶元素,补进对应文件的下...
  • 在vs2010实现归并排序功能的静态链接库 @author QinJingxuan 一、静态链接库的创建 1、新建项目myStaticLibTest 2、新建头文件staticTest.h void radixsort(int array[10]); 3、新建源文件staticTest.cpp...
  • 解析: 归并排序求逆序 #include<bits/stdc++.h> using namespace std; const int N=1e6+10000; typedef long long ll; int n; int a[N]; int tmp[N]; ll ans; void m(int l,int r) { if(l>=r) return ; ...
  • poj 2299_归并排序

    2013-05-02 10:24:16
    题目描述:   给一个序列,若只交换...——归并排序,在归并过程计算元素前推的位置。(比较两个相邻元素的排序方法可以做到稳定。)   代码:(注意500000个,最终的结果大于int能表示范围) #include #inc
  • 请你找出这两个正序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。你可以假设 nums1 和 nums2 不会同时为空。题解方法一、数组合并(归并)在两个有序的数组中要找到某个数,估计大家第一想到的就是归并的...
  • 我们可以先将这两个序列合并成一个升序序列,然后即可中位数,但是这样时间复杂度为O(n),空间复杂度也为O(n); 我们也可以采用归并排序的想法,先出两个序列的总元素的个数,因为他们等长,只需求出一个序列...
  • 要求:Median of Two Sorted Arrays(两个排序数组的中位数) 分析:1. 两个数组含有的数字总数为偶数或奇数两种...归并排序到一个新的数组,中位数。 代码: class Solution { public: double findMedi...
  • 题目:给定两个有序数组,都是按照从小到大排好序,它们合并后的中位数。   分析:在数据结构中我们学过,合并两个有序数组为一个有序数组的最好方法是归并排序。当然这只是归并排序的一 个子操作,这样的时间...
  • 算法1:最简单的办法就是把两个数组合并、排序,然后返回中位数即可,由于两个数组原本是有序的,因此可以用归并排序中的merge步骤合并两个数组。由于我们只需要返回中位数,因此并不需要真的合并两个数组,只需要...
  • python 中位数

    2020-08-17 01:06:27
    有⼀个⽆序的整数序列(⽆重复项,⻓度为奇数),请⽤你认为最优的⽅法序列的中位数。例如给 定数组 1、5、2、9、8、0、6,中位数是 5。要求算法的时间复杂度需要⼩于 O(n2),不能使⽤内置排 序函数,可以⽤任何语...
  • 归并排序 图文讲解归并思想归并排序,英文名称是MERGE-SORT。它是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列...
  • 文章目录题目思路一:外排序排序-归并)什么是外排序本题思路:先通过外排序进行排序再寻找中位数思路二:堆排序(转换为前5G大的元素)思路三:分而治之:基于二进制位映射分割思路四:基数排序(计数排序)...
  • 归并排序另一应用:数列的小和。问题描述:一个数列,如果左边的大,右边的小,则称这两个数位一个逆序对。 出一个数列有多少个逆序对。思路利用归并排序的过程完成逆序对问题。已知归并过程如下:1...

空空如也

空空如也

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

归并排序求中位数