1029. Median (25)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
	vector<vector<int> > arrays(2);
	int totalAmount = 0;
	for (int i = 0; i < 2; i++)
	{
		int amount;
		cin >> amount;
		totalAmount += amount;
		arrays[i].resize(amount, 0);
		for (int j = 0; j < amount; j++)
		{
			cin >> arrays[i][j];
		}
	}

	int position = (totalAmount-1) / 2;
	vector<int> &n1 = arrays[0], &n2 = arrays[1];
	if(n1.size()>n2.size())
	{
		n1.swap(n2);
	}
	
	int l = 0, r = n1.size() - 1;
	while(l<=r)
	{
		int p1 = l + ((r - l) >> 1);
		int p2 = position - p1;
		if(n1[p1]>=n2[p2])
		{
			r = p1 - 1;
		}else
		{
			l = p1 + 1;
		}
	}

	cout << max(l > 0 ? n1[r] : INT32_MIN, position - l < n2.size() ? n2[position - l] : INT32_MIN);

	return 0;
}

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++)
            a[i]=sc.nextInt();
        int m=sc.nextInt();
        int[] b=new int[m];
        for(int i=0;i<m;i++)
            b[i]=sc.nextInt();
        int[] result=new int[m+n];
        int aIndex=0,bIndex=0;
        for(int i=0;i<m+n;i++){
            if(aIndex<n && bIndex<m){
                if(a[aIndex]<b[bIndex]){
                    result[i]=a[aIndex++];
                }else{
                    result[i]=b[bIndex++];
                }
            }else{
                break;
            }
        }
        if(aIndex==n && bIndex!=m){
            for(int i=bIndex;i<m;i++){
                result[n+i]=b[i];
            }
        }else if(aIndex!=n && bIndex==m){
            for(int i=aIndex;i<n;i++){
                result[m+i]=a[i];
            }
        }
        System.out.println(result[(m+n-1)/2]);
    }
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
	int length, num;
	while (cin >> length)
	{
		vector<int> data;
		for (int i = 0; i < length; i++)
		{
			cin >> num;
			data.push_back(num);
		}
		cin >> length;
		for (int i = 0; i < length; i++)
		{
			cin >> num;
			data.push_back(num);
		}
		sort(data.begin(), data.end());
		cout << data[(data.size() - 1) / 2] << endl;
	}
	return 0;
}

__author__ = 'Yaicky'

while True:
    try:
        numList1 = map(int, raw_input().strip().split())
        numList1.remove(numList1[0])
        numList2 = map(int, raw_input().strip().split())
        numList2.remove(numList2[0])

        numList1.extend(numList2)
        numList1.sort()

        if len(numList1)%2:
            pos = len(numList1) / 2
        else:
            pos = len(numList1) / 2 - 1
        print numList1[pos]
    except:
        break


#内存超限  爆炸....

import java.util.Scanner;
//最后一个测试用例有毒，用collections.sort排序都超时，我们能写出更优的排序方法吗？
//显然不可能。于是只能换个思路，因为只要求中位数，所以直接比较就行了，不用排序（类似二路合并排序）
public class Main {

	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int m=in.nextInt();
		int a[]=new int[m];
		for(int i=0;i<m;i++){
			a[i]=in.nextInt();
		}
		int n=in.nextInt();
		int b[]=new int[n];
		for(int i=0;i<n;i++){
			b[i]=in.nextInt();
		}

		int loc=(m+n+1)/2;
		int count=0;
		int i=0;
		int j=0;
		int median=0;
		while(count<loc){
			if(a[i]<b[j]){
				median=a[i++];
			}else median=b[j++];
			count++;
		}
		System.out.println(median);
	}
}

a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = sorted(a[1:] + b[1:])
print(c[(a[0] + b[0] - 1) // 2])

a = list(map(int,input().split()))
b = list(map(int,input().split()))

if a[(a[0] + 1) // 2] > b[(b[0] + 1) // 2]:
    a,b = b,a
if a[-1] > b[1]:
    c = sorted(a[(a[0] + 1) // 2:] + b[1:(b[0] + 1) // 2 + 1])
    print(c[(a[0] + b[0] + 1) // 2 - (a[0] + 1) // 2])
else:
    if a[0] >= b[0]:
        print(a[(a[0] + b[0] + 1) // 2])
    else:
        print(b[(a[0] + b[0] + 1) // 2 - a[0]])

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int l1=scanner.nextInt();
        int[]S1=new int[l1];
        for(int i=0;i<l1;i++){
            S1[i]=scanner.nextInt();
        }

        int l2=scanner.nextInt();
        int[]S2=new int[l2];
        for(int i=0;i<l2;i++){
            S2[i]=scanner.nextInt();
        }

        int target=(l1+l2+1)/2;

        int cnt=0;
        for(int i=0,j=0;i<l1&&j<l2;){
            int s1=S1[i];
            int s2=S2[j];

            cnt++;

            if(s1<s2){
                if(cnt==target){
                    System.out.print(s1);
                    break;
                }
                i++;
            }else{
                if(cnt==target){
                    System.out.print(s2);
                    break;
                }
                j++;
            }
        }
    }
}

	

//1008.Median
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    vector<long long> v;
    int n,t; cin>>n;
    for(int i=0;i<n;i++){
        cin>>t; v.push_back(t);
    }
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>t; v.push_back(t);
    }
    sort(v.begin(), v.end()); //默认升序
    //cout<<v[v.size()%2==0?v.size()/2-1:v.size()/2];
    cout<<v[(v.size()-1)/2];
    return 0;
}

排序的时间复杂度的下限是Nlog(N),那我就用堆吧

a = list(map(int,input().split()))
b = list(map(int,input().split()))
lst = a[1:]+b[1:]
lst.sort()
if len(lst)%2!=0:
    print(lst[len(lst)//2])
else:
    print(lst[len(lst)//2-1])

思路：常规使用sort输出
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace  std;

int main()
{
    //ifstream cin("test.txt");
    int n1, n2;
    while (cin >> n1)
    {
        vector<int> v1(n1);
        for (int i = 0; i < n1; i++)
        {
            cin >> v1[i];
        }
        cin >> n2;
        int temp;
        for (int i = 0; i < n2; i++)
        {
            cin >> temp;
            v1.push_back(temp);
        }
        sort(v1.begin(), v1.end());
        cout << v1[v1.size() % 2 == 0 ? v1.size() / 2 - 1 : v1.size() / 2] << endl;
    }
    system("pause");
}

}

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

const int maxn = 1000000 + 10;

long a1[maxn * 2];
long a2[maxn];

bool read_list(long* a){
	string line;
	while(!getline(cin, line)) return false;
	stringstream ss(line);
	int x;
	int n = 0;
	while(ss >> x) a[n++] = x;
	return (n > 0);
}

int main(){
	if(read_list(a1))
		read_list(a2);
	for(int i=1;i<=a2[0];i++){
		a1[a1[0]+i] = a2[i];
	}
	sort(a1+1, a1+a1[0]+a2[0]+1);
	int n_sum = a1[0] + a2[0];
	int pos = (n_sum % 2 == 1)?(n_sum / 2 + 1):(n_sum / 2);
	cout << a1[pos] << endl;
	return 0;
}

//类似归并，但是还有会有部分例子超时
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		int[] arr1 = new int[N];
		for(int i=0;i<N;i++){
			arr1[i] = in.nextInt();
		}
		int M = in.nextInt();
		int[] arr2 = new int[M]; 
		for(int i=0;i<M;i++){
			arr2[i] = in.nextInt();
		}
		
		int[] arr = new int[M+N];
		int len = arr.length/2 + arr.length%2;
		int i=0;
		int j=0;
		for(int k=0;k<len;k++){
			if(arr1[i]<arr2[j]){
				arr[k]=arr1[i];
				i++;
			}else{
				arr[k]=arr2[j];
				j++;
			}
		}
		System.out.println(arr[len-1]);

	}
}