在两个排序数组中找到第k小的数

#include <bits/stdc++.h>

using namespace std;

int findKth(vector<int> a, vector<int> b, int k)
{
    // 总是让A的大小小于B
    if(a.size() > b.size())
        return findKth(b, a, k);

    //终止条件
    if(a.size() == 0)
        return b[k - 1];
    if(k == 1)
        return min(a[0], b[0]);

    int m = a.size();
    int n = b.size();

    int i = min(m, k / 2); // 如果大小不足k/2，取自身大小
    int j = k - i;

    if(a[i - 1] > b[j - 1])
        return findKth(a, vector<int>(b.begin() + j, b.end()), k - j);
    else if(a[i - 1] < b[j - 1])
        return findKth(vector<int>(a.begin() + i, a.end()), b, k - i);
    else
        return a[i-1];
}

int main(){
    vector<int> a,b;
    int a_len, b_len, k, x;
    cin >> a_len >> b_len >> k;
 
    for(int i = 0; i < a_len; i++){
        cin >> x;
        a.push_back(x);
    }
    
    for(int j = 0; j < b_len; j++){
        cin >> x;
        b.push_back(x);
    }
    
    int target = findKth(a, b, k);
    cout << target;
    
    return 0;
}

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

int main(){
    int n, m, k, x;
    cin>>n>>m>>k;
    priority_queue<int, vector<int>, greater<int> > q;
    for(int i=0;i<n;i++){
        cin>>x;
        if(i<k)
            q.push(x);
    }
    for(int i=0;i<m;i++){
        cin>>x;
        if(i<k)
            q.push(x);
    }
    while(k-->1)
        q.pop();
    cout<<q.top()<<endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,k;
    cin>>n>>m>>k;
    vector<int>arr1(n),arr2(m);
    multiset<int>s;
    for(int i=0;i<n;i++)
    {
        cin>>arr1[i];
        s.insert(arr1[i]);
    }
    for(int i=0;i<m;i++)
    {
        cin>>arr2[i];
        s.insert(arr2[i]);
    }
    set<int>::iterator it=s.begin();
    for(int i=0;i<k-1;i++)
        it++;
    cout<<*it<<endl;
    return 0;
}

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

int getUpmid(vector<int> a, int s1, int e1, vector<int> b, int s2, int e2){
    int mid1 = 0;
    int mid2 = 0;
    int offset = 0;
    while(s1 < e1){
        mid1 = s1+((e1-s1)>>1);
        mid2 = s2+((e2-s2)>>1);
        offset = ((e1-s1+1)&1)^1;
        if(a[mid1] < b[mid2]){
            s1 = mid1 + offset;
            e2 = mid2;
        }else if(a[mid1] > b[mid2]){
            e1 = mid1;
            s2 = mid2 + offset;
        }else return a[mid1];
    }
    return min(a[s1], b[s2]);
}
int getKth(vector<int> a, vector<int> b, int n, int m, int k){
    vector<int> shorts = n < m ? a : b;
    vector<int> longs = n >= m ? a : b;
    int s = shorts.size();
    int l = longs.size();
    if(k <= s) return getUpmid(shorts, 0, k-1, longs, 0, k-1);
    if(k > l){
        if(shorts[k-l-1] >= longs[l-1]) return shorts[k-l-1];
        if(longs[k-s-1] >= shorts[s-1]) return longs[k-s-1];
        return getUpmid(shorts, k-l, s-1, longs, k-s, l-1);
    }
    if(longs[k-s-1] >= shorts[s-1]) return longs[k-s-1];
    return getUpmid(shorts, 0, s-1, longs, k-s, k-1);
}
int main(){
    int n, m, k; scanf("%d%d%d", &n, &m, &k);
    vector<int> a(n), b(m);
    for(int i=0; i<(n+m); i++){
        if(i<n) scanf("%d", &a[i]);
        else scanf("%d", &b[i-n]);
    }
    cout << getKth(a, b, n, m, k);
    return 0;
}

# 题目要求是log的时间复杂度，利用自带的sort去排序，但是能accept
#  实际上目前最好的排序方法时间复杂度为nlog2n，所以该方法实际时间复杂度不符合题意
def Tow_find_K():
    n,m,k = list(map(int, input().split()))
    arr1 = list(map(int, input().split()))
    arr2 = list(map(int, input().split()))

    arr = arr1 + arr2
    arr.sort()
    print(arr[k-1])

if __name__ == '__main__':
    Tow_find_K()

#include "iostream"
#include  "vector"
#include  "set"
#include  "map"
#include  "limits.h"
#include  "algorithm"
using namespace std;

int process(vector<int> v1,vector<int> v2,int l1,int r1,int l2,int r2)
{
    int mid1 = (l1+r1)/2;
	int mid2 = (l2+r2)/2;
    vector<int> bigger;
    vector<int> smaller;
    int bigger_l,bigger_r;
    int smaller_l,smaller_r;
    
    if(v1[mid1] == v2[mid2])
        return v1[mid1];
    else if(v1[mid1] > v2[mid2])
    {
        bigger.assign(v1.begin(),v1.end());
        smaller.assign(v2.begin(),v2.end());
        bigger_l = l1;
        bigger_r = r1;
        smaller_l = l2;
        smaller_r = r2;
    }
    else
    {
        bigger.assign(v2.begin(),v2.end());
        smaller.assign(v1.begin(),v1.end());
        bigger_l = l2;
        bigger_r = r2;
        smaller_l = l1;
        smaller_r = r1;
    }
    
	bool odd = false;
	if((r1-l1+1) & 0x1 == 1)
		odd = !odd;		
	if(odd)
	{
		if(smaller[(smaller_l+smaller_r)/2] >= bigger[(bigger_l+bigger_r)/2-1])
            return smaller[(smaller_l+smaller_r)/2];
        else
            return process(bigger,smaller,bigger_l,(bigger_l+bigger_r)/2-1,(smaller_l+smaller_r)/2+1,smaller_r);
	}
	else
	{
			return process(bigger,smaller,bigger_l,(bigger_l+bigger_r)/2,(smaller_l+smaller_r)/2+1,smaller_r);
	}
}

int findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2,int k)
{
	vector<int> shortv;
	vector<int> longv;
	shortv = nums1.size() < nums2.size() ? nums1 : nums2;
	longv  = nums1.size() >= nums2.size() ? nums1 : nums2;
	
	if( k <=shortv.size())
	{
		return process(shortv,longv,0,k-1,0,k-1);//1<=k<=短的长度   取k个数求上中位数
	}
	else if(k > shortv.size() && k <= longv.size())//短的长度<=k<=长的长度   短的都能取到  长的取长-k - k长度
	{
		if(longv[k-shortv.size()-1] >= shortv[shortv.size()-1])//发现长的多一个，手动比较一下
			return longv[k-shortv.size()-1];
		else
			return process(shortv,longv,0,shortv.size()-1,k-shortv.size(),k-1);
	}
	else if(k > longv.size() && k <= shortv.size()+longv.size()) //k>长的长度   短的：k-长长度-最后有可能   长的：k - 短长度-最后有可能
	{
        //算出上中位数发现少了一个，那还有手动排除两个
		if(longv[k-shortv.size()-1] >= shortv[shortv.size()-1])
			return longv[k-shortv.size()-1];
		else if( shortv[k-longv.size()-1] >= longv[longv.size()-1])
			return shortv[k-longv.size()-1];
		else
			return process(shortv,longv,k-longv.size(),shortv.size()-1,k-shortv.size(),longv.size()-1); 
			
		
	}
}

//已知长度的输入
int main()
{
	int n,m,k;
	cin>>n>>m>>k;
	int in;
	vector<int> v1;
	vector<int> v2;
	while(n > 0)
	{
		cin>>in;
		v1.push_back(in);
		n--;
	}
		
	while(m > 0)
	{
		cin>>in;
		v2.push_back(in);
		m--;
	}
	
	cout<<findMedianSortedArrays(v1,v2,k)<<endl;
	return 0;
}