题目

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行，每行一个数字，代表这个序列；
输出：对于输出对应该组数据的逆序对的数量；
顺便在此吐槽一下翻译器，翻译了一顿我啥都看不懂（都怀疑自己是不是中国人了），幸亏自己还能看懂点英语啊。
这个题是机房里一位小伙伴问我我才做的，蒟蒻的我刚开始居然想要双重循环（类似于冒泡排序的方法）来做，看完数据范围之后就放弃了；
        然后想到了逆序对是使用归并排序来做的，所以就自己手码了一个归并排序；；可能有的小伙伴还不知道归并排序的思想，所以看了一晚上归并排序的蒟蒻——我，就来给小伙伴们介绍一下吧！
归并排序：
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

题目：一个长度为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的中位数。要求：

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

该题为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的中位数过程如下：


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


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


若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分。


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

以前没有学过归并排序，所以这次研究逆序对很是困难。
感谢这位大神，让我终于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;
}