408每日算法——求第k大的数（2018年武汉大学933）

时间：2021-07-09 00:36:48 收藏：0 阅读：19

求第K大的数

一、问题描述

　　两个整数递增有序序列A，B分别有n和m个元素，求第K大的数（1≤k≤n+m），要求算法有最佳时间复杂度

　　例子：

　　　　输入

　　　　A={1,3,4,5,6}

　　　　B={3,4,5,6}

　　　　K=4

　　　　输出

二、分析过程

　　因为给出的两个数组是有序的数组，所以不需要对数组进行排序了，为了保证最优时间复杂度和空间复杂度，应尽可能做到一次遍历和常数级空间。

　　最先想到的算法就是双指针法了，给A一个指针，给B一个指针，依次向后移动两个指针，当两个指针共移动k-2次时就找到了第k大的元素

三、算法设计

　　定义两个指针i和j分别指向A和B的起始位置，当i.value<=j.value时i++，当j.value<=i.value时j++，选择小的值作为res，每次移动后count++，当count=k时结束循环，如果有一个数组被遍历完就只遍历另一个数组。

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 int main(){
 5     int n,m,k;
 6     scanf("%d%d%d",&n,&m,&k);
 7     int A[n],B[m];
 8     for(int i=0;i<n;i++){
 9         scanf("%d",&A[i]);
10     }
11     for(int i=0;i<m;i++){
12         scanf("%d",&B[i]);
13     }
14     //上面是构造测试用例
15     int i=-1,j=-1,res=0,count=0;//i和j作为下标初值为-1这样可以让移动次数等于k，res用于返回结果
16     while(count<=k){
17         if(i<n&&j<m){//未出现越界时 
18             if(A[i]<=B[j]){
19                 i++;
20                 count++;
21             }else if(B[j]<A[i]){
22                 j++;
23                 count++;
24             }
25             res = min(A[i],B[j]);
26         }else if(i<n&&j>=m){
27             i++;
28             count++;
29             res = A[i];
30         }else if(i>=n&&j<m){
31             j++;
32             count++;
33             res = B[j];
34         }
35     }
36     printf("%d",res);
37     return 0;
38 }

原文：https://www.cnblogs.com/zyq79434/p/14988146.html