开发者社区> 华山青竹> 正文

3299 有序数组合并求第K大问题

简介: 题目描述 Description 给出两个有序数组A和B(从小到大有序),合并两个有序数组后新数组c也有序,询问c数组中第k大的数 假设不计入输入输出复杂度,你能否给出一个O(logN)的方法? 输入描述 Input Description 第一行输入三个整数n、m和k 第二行输入n...
+关注继续查看
题目描述 Description

给出两个有序数组A和B(从小到大有序),合并两个有序数组后新数组c也有序,询问c数组中第k大的数

假设不计入输入输出复杂度,你能否给出一个O(logN)的方法?

输入描述 Input Description

第一行输入三个整数n、m和k

第二行输入n个用空格隔开的整数表示数组A

第三行输入m个用空格隔开的整数表示数组B

输入保证A和B数组非递减

输出描述 Output Description

合并两个数组之后的第k大的数

样例输入 Sample Input

2 3 4

1  2

1 1 5

样例输出 Sample Output

2

数据范围及提示 Data Size & Hint

1<=n,m<=1000000

1<=k <=n+m

算法一:O(m+n+k)

做类似于归并排序的合并,但是没有使用额外的空间。

 1 #include <stdio.h>
 2 long long n,m,k,a[1000005],b[1000005];
 3 long long findKthSMallest()
 4 {
 5     int ai=0,bi=0;
 6     while(k>0)
 7     {
 8         if(ai<n&&bi<m)
 9         {
10             if(a[ai]<=b[bi]) 
11             {
12                 if(k==0) return a[ai];
13                 ai++;
14             }
15             else if(b[bi]<=a[ai])
16             {
17                 if(k==0) return b[bi];
18                 bi++;
19             }
20         }
21         else if(ai<n&&bi==m)
22         {
23             if(k==0) return a[ai];
24             ai++;
25         }
26         else if(ai==n&&bi<m)
27         {
28             if(k==0) return b[bi];
29             bi++;
30         }
31         else return -1;
32         
33         k--;
34     }
35 }
36 int main(int argc, char *argv[])
37 {
38     int i;
39     scanf("%d%d%d",&n,&m,&k);
40     for(i=0;i<n;i++) scanf("%d",&a[i]);
41     for(i=0;i<m;i++) scanf("%d",&b[i]);
42     printf("%d\n",findKthSMallest());
43     return 0;
44 }
View Code

下面的代码是同样的思路,但是代码比较简洁易懂:

 1 #include <stdio.h>
 2 int n,m,k,a[1000005],b[1000005];
 3 int findKthSMallest(int a[],int n,int b[],int m,int k)
 4 {
 5     int a_offset = 0, b_offset = 0;
 6     if(n+m<k) return -1;
 7     
 8     while(true)
 9     {
10         if(a_offset<n)
11         {
12             while (b_offset == m || a_offset<n&&a[a_offset] <= b[b_offset])
13             {
14                 if(a_offset+1 + b_offset == k) return a[a_offset];
15                 a_offset++;
16             }
17         }
18         if(b_offset<m)
19         {
20             while (a_offset == n || b_offset<m&&a[a_offset] >= b[b_offset])
21             {
22                 if (a_offset + b_offset+1 == k) return b[b_offset];
23                 b_offset++;
24             }
25         }
26     }
27 }
28 int main(int argc, char *argv[])
29 {
30     int i;
31     scanf("%d%d%d",&n,&m,&k);
32     for(i=0;i<n;i++) scanf("%d",&a[i]);
33     for(i=0;i<m;i++) scanf("%d",&b[i]);
34     printf("%d\n",findKthSMallest(a,n,b,m,k));
35     return 0;
36 }

第二段代码参考自:在线疯狂的博客,原文代码有误,已经修正。

第三种写法:省一些空间,b[ ]并没有提前完整输入。

 1 #include <stdio.h>
 2 int n,m,k,a[1000005];
 3 int main(int argc, char *argv[])
 4 {
 5     int i,j,bTemp,kIndex,kValue=0,f;
 6     scanf("%d%d%d",&n,&m,&k);
 7     for(i=0;i<n;i++) scanf("%d",&a[i]);
 8 
 9     i=0,kIndex=0,f=0;
10     for(j=0;j<m||i<n;j++) // i是a[]的下标,j是b[]的下标 
11     {
12         //for的语句条件和这里的if条件是防止b[]扫描完了却未曾寻找到第k个数.
13         //这个时候需要继续循环,在a[]中寻找,但是不再输入 
14         if(j<m) scanf("%d",&bTemp);
15         
16         while(i<n||j<m)
17         {
18             if(j==m||i<n&&a[i]<=bTemp)
19             {
20                 kIndex++;
21                 kValue=a[i++];
22                 if(kIndex==k) { f=1; break; }
23             }
24             else
25             {
26                 kIndex++;
27                 kValue=bTemp;
28                 if(kIndex==k) f=1;
29                 break;
30             }
31         }
32         if(f==1) break;
33     }
34     printf("%d\n",kValue);
35     return 0;
36 }
View Code

 

 

算法二:时间复杂度O(log(n+m))。当然,假如考虑输入,那时间复杂度仍然是O(n+m)

代码来源:http://www.cnblogs.com/swanspouse/p/5285015.html

代码解析:

  • 传统解法,最直观的解法是O(m+n)。直接merge两个数组,然后求第K大的数字。

  • 如果想要时间复杂度将为O(log(m+n))。我们可以考虑从K入手。如果我们每次能够删除一个一定在第K个元素之前的元素,那么我们需要进行K次,但是如果每次我们都删除一半呢?由于两个数组都是有序的,我们应该充分利用这个信息。

    • 假设A B 两数组的元素都大于K/2,我们将A B两数组的第K/2个元素进行比较。比较的结果有三种情况。
      • A[K/2] == B[K/2]
      • A[K/2] > B[K/2]
      • A[K/2] <= B[K/2]
    • 如果 A[K/2] < B[K/2] 意味着 A[0] 到 A[K/2] 肯定在A∪B的前k个元素中。因此我们可以放心删除A数组的这个k/2个元素。同理A[K/2] > B[K/2]。
    • 如果 A[K/2] == B[K/2] 说明已经找到了第K个元素,直接返回A[K/2]或者B[K/2]。
 1 #include <stdio.h>
 2 #include <iostream>
 3 using namespace std;
 4 int a[1000005],b[1000005];
 5 int find_kth(int A[],int m, int B[], int n, int k)
 6 {
 7     if(m > n )  return find_kth(B, n, A, m, k);
 8     if( m == 0) return B[k-1];
 9     if( k == 1) return min(A[0], B[0]);
10 
11     int ia = min(k /2, m);
12     int ib = k -ia;
13     if( A[ia-1] < B[ib -1]) 
14         return find_kth(A +ia, m -ia, B, n, k -ia);
15     else if( A[ia-1] > B[ib-1])
16         return find_kth(A, m, B +ib, n -ib, k -ib);
17     else
18         return A[ia-1];
19 }
20 int main(int argc, char *argv[])
21 {
22     int i,n,m,k;
23     int ans;
24     scanf("%d%d%d",&n,&m,&k);
25     for(i=0;i<n;i++) scanf("%d",&a[i]);
26     for(i=0;i<m;i++) scanf("%d",&b[i]);
27     ans=find_kth(a,n,b,m,k);
28     printf("%d\n",ans);
29     return 0;
30 }

说明

  • 注意其中的递归终止条件。
  • 将求第K大元素的问题划分成为子问题,不断的对问题进行缩小,采取递归的方式求解。
  • 此问题可以进行拓展,比如求两有序数组的中位数。

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
14225 0
如何设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云安全组设置详细图文教程(收藏起来) 阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程。阿里云会要求客户设置安全组,如果不设置,阿里云会指定默认的安全组。那么,这个安全组是什么呢?顾名思义,就是为了服务器安全设置的。安全组其实就是一个虚拟的防火墙,可以让用户从端口、IP的维度来筛选对应服务器的访问者,从而形成一个云上的安全域。
19005 0
洛谷 P2822 组合数问题
Noip2016提高组day2 T1   题目描述   组合数表示的是从n个物品中选出m个物品的方案数。举个例子,从(1,2,3) 三个物品中选择两个物品可以有(1,2),(1,3),(2,3)这三种选择方法。
835 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
28221 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,大概有三种登录方式:
13156 0
【组合数学】非降路径问题 ( 非降路径问题概要说明 | 非降路径问题基本模型 | 非降路径问题拓展模型 1 非原点起点 | 非降路径问题拓展模型 2 有途经点 )
【组合数学】非降路径问题 ( 非降路径问题概要说明 | 非降路径问题基本模型 | 非降路径问题拓展模型 1 非原点起点 | 非降路径问题拓展模型 2 有途经点 )
42 0
3299 有序数组合并求第K大问题
题目描述 Description 给出两个有序数组A和B(从小到大有序),合并两个有序数组后新数组c也有序,询问c数组中第k大的数 假设不计入输入输出复杂度,你能否给出一个O(logN)的方法? 输入描述 Input Description 第一行输入三个整数n、m和k 第二行输入n...
1311 0
阿里云服务器安全组设置内网互通的方法
虽然0.0.0.0/0使用非常方便,但是发现很多同学使用它来做内网互通,这是有安全风险的,实例有可能会在经典网络被内网IP访问到。下面介绍一下四种安全的内网互联设置方法。 购买前请先:领取阿里云幸运券,有很多优惠,可到下文中领取。
22144 0
+关注
华山青竹
一个喜欢玩代码的小青年呵呵呵
543
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载