在两个有序的数组中找第N个数,二分查找 O(lgm+lgn)级-阿里云开发者社区

开发者社区> 云栖希望。> 正文

在两个有序的数组中找第N个数,二分查找 O(lgm+lgn)级

简介:
+关注继续查看

问题描述:

Give a divide and conquer algorithm for the following problem:
you are given two sorted lists of size m and n, and are allowed 
unit time access to the ith element of each list. Give an O(lg m + lgn) 
time algorithm for computing the kth largest element in the union of the  two lists. (For simplicity, you can assume that the elements of the 
two lists are distinct).

问题分析:

1. 把 A 平均分为前后两个部分,前部分有 x 个元素,后部分有 n-x 个元素

(由于 A 是有序的,所以后一部分的所有元素大于前一部分)。A[x] = A的

后一部分的第一个元素。

 


2. 同理把 B 也平均分成前后两个部分,前部分有 y 个元素,后部分有 m-y 个元素。 
B[y] = B的后一部分的第一个元素。


3. 由于两个数组都是被平均分割的,所以可以近似地认为 x = n/2, y = m/2。 
这里不妨设 A[x] <= B[y](如果 A[x] > B[y] 处理过程和下面类似): 

 

part1:

 
由于在 A 中,A[x] 前面有 x 个元素,在 B 中,B[y] 前面有 y 个元素, 
并且又有 A[x] <= B[y],那么,合并以后,A[x]前面原来那些元素必然 
也在B[y]前面,也就是说,B[y]前面至少会有 x + y 个元素,我们再规定 
如果 A, B 中有相同元素,则合并后 A 中的元素排在 B 前面,那么归并 
以后 A[x] 也会排在 B[y] 前面,于是乎合并之后 B[y] 至少有 x+y+1 个元素。 
 
如果 k <= x+y+1,也就是说,合并后第 k 大的元素必然落在 B[y] 前面。 
所以,原来在 B 数组中,第二部分(B[y]以及 B[y] 之后)那些元素都不可能 
包含我们要找到内容(第 k 大元素),所以我们可以把他们排除掉。 
这样就排除了 B 中一半的内容。 
 
 

part2:

 
在 A 中,A[x] 及其后面有 n1-x 个元素,除去 A[x] 之后有 n-x-1 个元素, 
B[y] 及其后面有 m-y 个元素。那么,由于 A[x] <= B[y],所以合并起来之后, 
B[y] 后面那些元素必然也在 A[x] 后面,则合并后 A[x] 后面至少有  
(n-x-1) + (m-y) = (n+m)-(x+y+1) 个元素。 
 
如果 k > x+y+1,也就说,合并后第 k 大的元素必然落在 A[x] 后面。 
所以,原来在 A 数组中,第一部分(A[x]之前)以及 A[x] 都不可能包含我们 
要找的元素,所以我们可以把他们排除掉。这样就排除了 A 中一半的内容。 
 
 

all:

 
综上所诉,对于 k <= x+y+1 还是 k > x+y+1 我们都提出了解决的方案,并且每种方案 
都能把 A 或者 B 的规模减小一半。减小了一半之后,我们将其作为一个新的问题 
继续使用上面的算法处理,直到 A 或者 B 减小到足够小: 
 
1. A没有了,这样只需要找出 B 中第 k 大的元素,也就是 B[k]. 
2. B没有了,同上结果就是 A[k].

 

代码如下:

 

[c-sharp] view plaincopy
  1. /************************************************************************ 
  2.  * This is the practice1 of the Algorithms It solved the problem1 below: 
  3.  *  
  4.  * Give a divide and conquer algorithm for the following problem: 
  5.  * you are given two sorted lists of size m and n, and are allowed  
  6.  * unit time access to the ith element of each list. Give an O(lg m + lgn)  
  7.  * time algorithm for computing the kth largest element in the union of the  
  8.  * two lists. (For simplicity, you can assume that the elements of the  
  9.  * two lists are distinct). 
  10.  *  
  11.  * The idea of the Algorithm in the help file idea.txt!! 
  12.  * 
  13.  * The Algorithm is designed by:Nanne 
  14.  *           
  15.  ************************************************************************/  
  16. #include <iostream>  
  17. using std::cin;  
  18. using std::cout;  
  19. using std::endl;  
  20. int FindTheKth(int a[],int b[],int aLeft, int aRight, int bLeft, int bRight, int k);  
  21.    
  22. int main(){  
  23.     int sizeA,sizeB;  
  24.     int Kth;  
  25.     cout << "AĴС";  
  26.     cin >> sizeA;  
  27.     int *arrA = new int[sizeA];  
  28.     cout << "" << sizeA << "" << endl;  
  29.     for (int i = 0; i < sizeA; i++)   
  30.         cin >> arrA[i];  
  31.     cout << "BĴС";  
  32.     cin >> sizeB;  
  33.     int *arrB = new int[sizeB];  
  34.     cout << "" << sizeB << "" << endl;  
  35.     for (int i = 0; i < sizeB; i++)   
  36.         cin >> arrB[i];  
  37.     while(true){  
  38.         cout << "õڼλ" << endl  
  39.             << "λҪ" << sizeA + sizeB << "(-1Ƴ):";  
  40.         cin >> Kth;  
  41.         if( Kth != -1){  
  42.             int res = FindTheKth(arrA,arrB,0, sizeA - 1, 0, sizeB - 1, Kth);  
  43.             if(res != -1)  
  44.                 cout << "" << Kth << "λǣ" << res << endl;  
  45.         }  
  46.         else  
  47.             return 0;  
  48.     }  
  49. }  
  50.   
  51. int FindTheKth(int a[],int b[],int aLeft, int aRight, int bLeft, int bRight, int k) {  
  52.     int aMid = (aLeft + aRight) / 2, bMid = (bLeft + bRight) / 2;  
  53.     if (aLeft > aRight) return b[bLeft+k-1];  
  54.     if (bLeft > bRight) return a[aLeft+k-1];  
  55.     if (a[aMid] <= b[bMid]) {  
  56.         if (k <= (aMid - aLeft) + (bMid - bLeft) + 1) {  
  57.             return FindTheKth(a,b,aLeft, aRight, bLeft, bMid-1, k);  
  58.         } else {  
  59.             return FindTheKth(a,b,aMid+1, aRight, bLeft, bRight, k-(aMid-aLeft)-1);  
  60.         }  
  61.     } else {  
  62.         if (k <= (aMid - aLeft) + (bMid - bLeft) + 1) {  
  63.             return FindTheKth(a,b,aLeft, aMid-1, bLeft, bRight, k);  
  64.         } else {  
  65.             return FindTheKth(a,b,aLeft, aRight, bMid+1, bRight, k-(bMid-bLeft)-1);  
  66.         }  
  67.     }  
  68.     return -1;  
  69. }  

本文转自博客园知识天地的博客,原文链接:在两个有序的数组中找第N个数,二分查找 O(lgm+lgn)级,如需转载请自行联系原博主。

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

相关文章
js实现二分查找
二分查找,也称为折半查找,是指在有序的数组里找出指定的值,返回该值在数组中的索引。查找步骤如下:  (1)从有序数组的最中间元素开始查找,如果该元素正好是指定查找的值,则查找过程结束。
638 0
二分查找算法
十大算法之二分查找: 二分查找算法是在有序数组中用到的较为频繁的一种算法,在未接触二分查找算法时,最通用的一种做法是,对数组进行遍历,跟每个元素进行比较,其时间为O(n).但二分查找算法则更优,因为其查找时间为O(lgn),譬如数组{1, 2, 3, 4, 5, 6, 7, 8, 9},查找元素6,用二分查找的算法执行的话,其顺序为:     1.第一步查找中间元素,即5,由于56,则6应该在7左边的数组元素中,那么只剩下6,即找到了。
624 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
4519 0
使用OpenApi弹性释放和设置云服务器ECS释放
云服务器ECS的一个重要特性就是按需创建资源。您可以在业务高峰期按需弹性的自定义规则进行资源创建,在完成业务计算的时候释放资源。本篇将提供几个Tips帮助您更加容易和自动化的完成云服务器的释放和弹性设置。
7830 0
查找类算法之二分搜索树 | 算法必看系列十
二分搜索树是为了实现快速查找而生的,也支持快速添加和删除一个数据。如何查找某个元素首先跟根节点去做比较,如果相等的话就返回;如果待查元素要比根节点小,就进行左子树递归查找;如果待查元素要比根节点大,就进行右子树的递归查找;如果查找到最后还没有一个符合的元素,就返回null。
494 0
linux下练习 c++ 二分查找
#include using namespace std; class person { string name; int age; public: person(const char* n,int a):name(n),age(a){} friend bool operator b.
631 0
+关注
云栖希望。
我是个随便的人
761
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载