大家好，又见面了，我是全栈君。
两个有序数组，各自含有n个元素，求第n大的元素
1.顺序遍历两个数组，计数变量k统计出现的第k小元素，时间复杂度为O(n)
代码例如以下：
int getmid(int a[],int b[],int n)
{
int k=0;
int i=0,j=0;
while(i<n&&j<n)
{
if(a[i]<b[j])
{
i++;
k++;
if(k==n)
return a[i-1];
}
else
{
j++;
k++;
if(k==n)
return b[j-1];
}
}
}
2.二分的方法
取A数组的中间元素mid1,取B数组的中间元素mid2,先比較这两个元素的大小。假设这两个元素相等，则直接返回A[mid1],假设A[mid1]<B[mid2],则mid1左側的元素能够去掉，B数组右側的元素能够去掉。这里还要区分数组元素个数为偶数奇数的情况，假设元素个数为偶数，则mid1元素也要去掉。假设A[mid1]<B[mid2]的情况与此类似。时间复杂度为O(logn)
# include <iostream>
# include <cstdlib>
using namespace std;
int mid(int a[],int b[],int n)
{
int s1=0,e1=n-1;
int s2=0,e2=n-1;
int mid1=(s1+e1)/2;
int mid2=(s2+e2)/2;
while(s1!=e1||s2!=e2)
{
mid1=(s1+e1)/2;
mid2=(s2+e2)/2;
if(a[mid1]==b[mid2])
{
return a[mid1];
}
if(a[mid1]<b[mid2])
{
if((s1+e1)%2==0)
{
s1=mid1;
e2=mid2;
}
else
{
s1=mid1+1;
e2=mid2;
}
}
else
{
if((s1+e1)%2==0)
{
e1=mid1;
s2=mid2;
}
else
{
e1=mid1;
s2=mid2+1;
}
}
}
return a[s1]<b[s2]?a[s1]:b[s2];}int main(){ int a[5]={2,4,5,6,9}; int b[5]={1,3,7,8,10}; cout<<mid(a,b,5)<<endl; system("pause"); return 0;}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/115644.html原文链接：https://javaforall.net
