#include <iostream>
using namespace std;
int a[1000010],b[1000010];
const int INF=99999999;
int main(){
    int n,m;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    cin>>m;
    for(int i=0;i<m;i++)
        cin>>b[i];
    a[n]=b[m]=INF;         //给定数组值的上限，使一个数组扫描完但没到mid时不会越界
    int mid=(n+m-1)/2;     //减1是为了统一奇偶数标准
    int j=0,k=0,num=0,s;
    while(j<n || k<m){
        if(a[j]<b[k]){
            s=a[j];
            j++;
        }
        else{
            s=b[k];
            k++;
        }
        if(num==mid) break;
        num++;
    }
    cout<<s;
    return 0;
}

咋没人用vector呀 这么好用的STL（手动滑稽）

#include <bits/stdc++.h>
using namespace std;
int main(){
	vector<int>a,b,c;
	int n1,n2,x;
	cin>>n1;
	while(n1--){
		cin>>x;
		a.push_back(x);
	}
	cin>>n2;
	while(n2--){
		cin>>x;
		b.push_back(x);
	}
	c.insert(c.end(),a.begin(),a.end());
	c.insert(c.end(),b.begin(),b.end());
	sort(c.begin(),c.end());
	if(c.size()%2==1) cout<<c[c.size()/2];
	else cout<<c[c.size()/2-1];
	return 0;
}

//其实有复杂度为o(n+m)的算法，就是比较两个数组，取出数组中较小的放到新数组
//这里用到的比较省事，用sort把所有都排序，直接输出，复杂度o((m+n)log(m+n))
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int n;
    while(cin>>n){
        int* a=new int[n];
        for(int i=0;i<n;i++)
            cin>>a[i];
        int m;
        cin>>m;
        int* b=new int[n+m];
        for(int i=0;i<n;i++)
            b[i]=a[i];
        for(int i=n;i<m+n;i++)
            cin>>b[i];
        sort(b,b+m+n);
        if((m+n)%2==0)
            cout<<b[(m+n)/2-1]<<endl;
        else
            cout<<b[(m+n)/2]<<endl;
    }
}

def getMedianNum(array1, array2):
    array_len_1 = len(array1)
    array_len_2 = len(array2)
    if array_len_1 > array_len_2:     #保持array1为数组长度小的那个
        array_len_1, array_len_2, array1, array2= array_len_2, array_len_1, array2, array1
    indexMin = 0        #在array1中查找的左下标
    indexMax = array_len_1    #在array1中查找的右下标
    mid_len = (array_len_1 + array_len_2 + 1) // 2  #在这里把数组个数平均分，如果为奇数，则左边多一个
    while indexMin <= indexMax:
        leftIndex = (indexMax + indexMin) // 2  #这个是array1分到左边元素的个数，在此一直二分查找
        rightIndex = mid_len - leftIndex    #这个是array2分到左边元素的个数，所以这里一直保持着左右平均分数组
        #leftIndex+rightIndex一直等于mid_len
        #如果第二个数组分到左边的最大数比第一个数组分到右边的最小数要大
        if leftIndex < array_len_1 and array2[rightIndex - 1] > array1[leftIndex]:
            #则分割数组，array要从左边拿回来一点元素（上面有保持平分数组）
            #分割leftIndex都不满足了，那么就在leftIndex+1的右边继续查找
            indexMin = leftIndex + 1
        #如果第一个数组在左边的最大数比第二个数组在左边的最小数要大
        elif leftIndex > 0 and array1[leftIndex - 1] > array2[rightIndex]:
        #则分割数组，array1要给多一点右边元素
        #leftIndex都不满足了，那么只能在leftIndex-1的左边继续查找
            indexMax = leftIndex - 1
        else:
            if leftIndex == 0:
                max_of_left = array2[rightIndex - 1]
            elif rightIndex == 0:
                max_of_left = array1[leftIndex - 1]
            else:
                max_of_left = max(array1[leftIndex - 1], array2[rightIndex - 1])
            return max_of_left

try:
    while True:
        array1 = list(map(int,input().split()))
        array2 = list(map(int,input().split()))
        print(getMedianNum(array1[1:],array2[1:]))
except Exception:
    pass

python解法

只需要把两个数组合起来排序，再输出中位数即可，所以只需要两行代码：

while True:
    try:

        APlusB=sorted(list(map(int,input().split()[1:]))+list(map(int,input().split()[1:])))
        print(APlusB[len(APlusB)//2] if len(APlusB)%2==1 else APlusB[len(APlusB)//2-1])


    except:
        break

通过测试。

如果你知道merge sort算法那么很容易理解下面的解题方法。

• 使用merge sort中merge的方法，因为两个数组是排好序的，所以只需要依次从两个数组选取小的值放入总的数组中即可。
  • 实现细节：设置两个游标i，j指向两个数组的队首，将arr[i]与arr[j]进行比较，如果arr[i]小，则把它放入数组中，i+1，再进行比较。
• 取中位数的时候，元素的下标为（n+m-1）/2,注意别忘记-1！！！

  #include
  #include
  using namespace std;
  int main() {
    int n, m;
    vector arr1;
    vector arr2;
    scanf("%d", &n);
    for (long i = 0; i < n; ++i)
    {
        long num;
        scanf("%ld", &num);
        arr1.push_back(num);
    }
    scanf("%d", &m);
    for (int i = 0; i < m; ++i)
    {
        long num;
        scanf("%ld", &num);
        arr2.push_back(num);
    }
    vector all_num;
    int i = 0;
    int j = 0;
    for (; i < arr1.size() && j < arr2.size();)
    {
        if(arr1[i] < arr2[j]) {
            all_num.push_back(arr1[i++]);
        }
        else {
            all_num.push_back(arr2[j++]);
        }
    }
    while(i < arr1.size()) {
        all_num.push_back(arr1[i++]);
    }
    while(j < arr2.size()) {
        all_num.push_back(arr2[j++]);
    }
    int idx = (n + m-1) / 2;
    printf("%ld\n", all_num[idx]);
  }

#include <iostream>
#include "vector"
#include <algorithm>
using namespace std;
int main(){
    int n, m;
    while(cin >> n && n!=0){
        vector<int> vec;
        int temp;
        for(int i=0; i<n; ++i){
            cin >> temp;
            vec.push_back(temp);
        }
        cin >> m;
        while(m--){
            cin >> temp;
            vec.push_back(temp);
        }
        sort(vec.begin(), vec.end());
        cout << vec[(vec.size()-1)/2];
    }
}

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 2000001;

int main() {
    int n1, n2;
    while (cin >> n1) {
        vector<int>arr(MAXN);
        for (int i = 0; i < n1; i++) {
            cin >> arr[i];
        }
        cin >> n2;
        for (int i = n1; i < n1 + n2; i++) {
            cin >> arr[i];
        }
        sort(arr.begin(), arr.begin() + n1 + n2);
        cout << arr[(n1 + n2 - 1) / 2] << endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int Max=2e6+10;
int b[Max];

int main() {
    ios::sync_with_stdio(0);
	int n,index=0;
	for(int i=0; i<2; i++) {
		cin>>n;
		int a[2][n];
		for(int j=0; j<n; j++) {
			cin>>a[i][j];
			b[index++]=a[i][j];
		}
	}
	sort(b,b+index);
	cout<<b[(index-1)/2]<<endl;
	return 0;
}

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 1000010;//这个长度用DEVC会崩，但是小于这个长度就不能AC，整了半天，日
int main() {
	int n1, n2, s1[maxn], s2[maxn];
//	while(1) {
		cin >> n1;
		for(int i = 0; i < n1; ++i) cin >> s1[i];
		cin >> n2;
		for(int i = 0; i < n2; ++i) cin >> s2[i];
		int ans,i = 0, j = 0, k = 0;
		int len = (n1 + n2 + 1) / 2;
		for(; k < len && i < n1 && j < n2; ++k) {
			if(s1[i] < s2[j]) ans = s1[i++];
			else			  ans = s2[j++];
		}
		while(k < len && i < n1) {ans = s1[i++]; k++;} 
		while(k < len && j < n2) {ans = s2[j++]; k++;}
		cout << ans << endl;
//	}
	return 0;
} 

//Median (25分)
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int n;
vector<long long int> arrays;

int main() {
    for (int k = 0; k < 2; k++) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            long long int number;
            scanf("%lld", &number);
            arrays.push_back(number);
        }
    }
    sort(arrays.begin(),arrays.end());
    if(arrays.size()%2==0) printf("%lld",arrays[(arrays.size()/2)-1]);
    else printf("%lld",arrays[arrays.size()/2]);
}

//   left part      |   right part
//S1[0].....S1[i-1] | S1[i].....S1[m-1]
//S2[0].....S2[j-1] | S2[j].....S2[n-1]
//just need to guarantee 
//(1)len(left)=len(right)=>( i+j=m-i+n-j)=>(j=(m+n+1)/2)
//(2)max(left)<min(right)=>(S1[i-1]<S2[j]&& S2[j-1]<S1[i])
//always use i(j) to represent the middle index of S1,S2
//to ensure the len(left)=len(right) 
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
double getMiddle(vector<int> S1, vector<int> S2) {
	int m = S1.size();
	int n = S2.size();
	if (m > n) { // to ensure m<=n
		vector<int> temp; temp.assign(S1.begin(), S1.end()); S1 = S2; S2 = temp;
		int tmp = m; m = n; n = tmp;
	}

// i contains to [0,m]
	int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;

//you need to consitantly caculate the result
	    while (iMin <= iMax) {

//split S1 
		 int i = (iMin + iMax) / 2;

//split S2 according the Formula (j=(m+n+1)/2)

//why should add 1? 

//because because in the next step to caculate lefmax

//you can directly output max(S1[i-1],S2[j-1]) 

//the key point is to understand i-1(j-1)  
		 int j = halfLen - i;

//in this step you can remember the formula

//big minus, small add 

//you need to ensure i<imax 

//because i contained in the right part of S1
		if (i < iMax &&S2[j - 1] > S1[i]) {
			iMin = i + 1; // i is too small
		}
		else if (i > iMin && S1[i - 1] > S2[j]) {
			iMax = i - 1; // i is too big
		}
		else { // i is perfect
			int maxLeft = 0;

//if the left part of S1 is empty

//maxleft equals the part of max(S2)
			if (i == 0) { maxLeft = S2[j - 1]; }
			else if (j == 0) { maxLeft = S1[i - 1]; }
			else { maxLeft = max(S1[i - 1], S2[j - 1]); }
			 return maxLeft; 
		}
	}
	return 0.0;
}
int main() {
		vector<int> S1; int N; cin >> N;
		for (int i = 0; i < N; i++) {
			int tmp; cin >> tmp;
			S1.push_back(tmp);
		}
		vector<int>S2; int M; cin >> M;
		for (int i = 0; i < M; i++) {
			int tmp; cin >> tmp;
			S2.push_back(tmp);
		}
		cout << getMiddle(S1, S2) << endl;
}

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    vector<int>v;
    int n;
    while(getline(cin,s))
    {
        v.clear();
        stringstream sin(s);
        while(sin>>n)
        {
            v.push_back(n);
        }
        getline(cin,s);
        stringstream sin_(s);
        while(sin_>>n)
        {
            v.push_back(n);
        }
        sort(v.begin(),v.end());
        if(v.size()%2==0)
            cout<<v[v.size()/2]<<endl;
        else
            cout<<v[v.size()/2+1]<<endl;
      
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
    
int n, m, midpos, curpos = 0, arrpos = 0;
vector<int> arr;
    
int FindMid(){
    int temp;
    for(int i = 0; i < m; i++){
        cin >> temp;
        while(arr[arrpos] < temp){
            curpos++;
            if(curpos == midpos)
                return arr[arrpos];
            arrpos++;
        }
        if(++curpos == midpos)
            return temp;
    }
    for(; arrpos < n; arrpos++){
        curpos++;
        if(curpos == midpos)
            return arr[arrpos];
    }
    return -1;
}
    
int main(void){
    ios::sync_with_stdio(false);//去除与stdio的同步关系(此时再使用scanf会出错)，加快读入
    cin >> n;
    arr.resize(n + 1);
    for(int i = 0; i < n; i++)
        cin >> arr[i];
    arr[n] = 0x7fffffff;
    cin >> m;
    midpos = (n + m + 1) / 2;
    cout << FindMid() << endl;
}