题目描述
给定两个有序数组arr1和arr2，在给定一个整数k，返回两个数组的所有数中第K小的数。
例如：
arr1 = {1,2,3,4,5};
arr2 = {3,4,5};
K = 1;
因为1为所有数中最小的，所以返回1；
arr1 = {1,2,3};
arr2 = {3,4,5,6};
K = 4;
因为3为所有数中第4小的数，所以返回3；
要求：如果arr1的长度为N，arr2的长度为M，时间复杂度请达到O(log(min{M,N}))。
程序代码
#include <iostream>
#include <vector>
using namespace std;
int findKthNum(vector<int> arr1,vector<int> arr2,int kth){
int k1=0,k2=0,k3=0;
int len1=arr1.size();
int len2=arr2.size();
int m;
while(k3!=kth){
if(k1<len1 && k2<len2){
if(arr1[k1]<arr2[k2]){
m=arr1[k1];
k1++;
}else{
m=arr2[k2];
k2++;
}
}else if(k1<len1 && k2>=len2){
m=arr1[k1];
k1++;
}else if(k1>=len1 && k2<len2){
m=arr2[k2];
k2++;
}else{
break;
}
k3++;
}
return m;
}
int main(){
vector<int> arr1;
arr1.push_back(2);
arr1.push_back(3);
arr1.push_back(4);
arr1.push_back(6);
arr1.push_back(8);
vector<int> arr2;
arr2.push_back(1);
arr2.push_back(5);
arr2.push_back(7);
cout<<findKthNum(arr1,arr2,5)<<endl;
system("pause");
}