3299 有序数组合并求第K大问题-白红宇

题目描述 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

数据范围及提示 Data Size & Hint

1<=n,m<=1000000

1<=k <=n+m

算法一：O（m+n+k）

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

1 #include 
      
        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

View Code

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

1 #include 
     
       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
      
       = 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

第二段代码参考自：，原文代码有误，已经修正。

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

1 #include 
      
        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

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 
     
       2 #include 
      
        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     else18         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

说明

注意其中的递归终止条件。

将求第K大元素的问题划分成为子问题，不断的对问题进行缩小，采取递归的方式求解。

此问题可以进行拓展，比如求两有序数组的中位数。