求两个有序的数列中第k小的数
作者:
毛里@Myers
,
2024-07-19 10:50:52
,
所有人可见
,
阅读 1
#include <iostream>
using namespace std;
const int N =1010;
int a[N],b[N];
int n,m,k;
int kminnum(int st1,int st2,int k)
{
int len1 = n-st1;
int len2 = m-st2;
if(len1==0)return b[st2+k-1];
if(len2==0)return a[st1+k-1];
if(k==1)return min(a[st1],b[st2]);
int i = st1 + min(k/2,len1)-1;
int j = st2 + min(k/2,len2)-1;
if(a[i] > b[j])return kminnum(st1,j+1,k-(j-st2+1));
else return kminnum(i+1,st2,k-(i-st1+1));
}
int main()
{
cin>>n>>m>>k;
for(int i=0 ; i<n ; i++)cin>>a[i];
for(int i=0 ; i<m ; i++)cin>>b[i];
int num = kminnum(0,0,k);//三个参数分别为要比较的两个数组,和寻找的第k小的数
cout<<num;
return 0;
}