题目原文
Selection in two sorted arrays. Given two sorted arrays a[] and b[], of sizes n1 and n2, respectively, design an algorithm to find the kth largest key. The order of growth of the worst case running time of your algorithm should be logn, where n = n1 + n2.
Version 1 : n1 = n2 and k = n/2
Version 2: k = n/2
Version 3: no restrictions
分析：
这个题目是要求从两个有序数组中寻找第K大元素，直观解法就是把连个数组归并排序，这样时间复杂度就是O(n)，但是题目只要求知道第K大元素，其余比K大的元素的排列顺序并不关心。
默认数组a和数组b都是从小到大排序的。不论第K大元素在a或b中，其右侧元素一定大于K，可考虑分别从a和b中排除右侧(k-1)/2个元素，剩下的就是在未排除区间寻找第(k-已排除元素)大元素。通过递归逐步缩小比较范围。具体算法见如下代码。
1 package week3; 2 3 import java.util.Arrays; 4 import edu.princeton.cs.algs4.StdRandom; 5 6 public class KthInTwoSortedArrays { 7 /** 8 * 寻找第K大元素 9 * @param a 数组a 10 * @param alo a的查找区间下界 11 * @param ahi a的查找区间上界 12 * @param b 数组b 13 * @param blo b的查找区间下界 14 * @param bhi b的查找区间上界 15 * @param k 当前查找区间的第k大元素 16 * @return 17 */ 18 private static int find(int[] a, int alo, int ahi,int[] b, int blo, int bhi, int k){ 19 if(alo > ahi) return b[bhi-k+1]; 20 if(blo > bhi) return a[ahi-k+1]; 21 if(k==1) return a[ahi] > b[bhi]? a[ahi]:b[bhi]; 22 //直接用bhi-(k-1)/2或ahi-(k-1)/2进行查找可能会将第K个元素给漏掉 23 int bt = bhi-(k-1)/2 > blo ? bhi-(k-1)/2:blo; 24 int at = ahi-(k-1)/2 > alo ? ahi-(k-1)/2:alo; 25 if(a[at] >= b[bt]) 26 return find(a,alo,at-1,b,blo,bhi,k-(ahi-at+1)); 27 else 28 return find(a,alo,ahi,b,blo,bt-1,k-(bhi-bt+1)); 29 } 30 31 public static void main(String[] args){ 32 int n = 10; 33 int n1 = StdRandom.uniform(n); 34 int n2 = n-n1; 35 int[] a = new int[n1]; 36 int[] b = new int[n2]; 37 for(int i=0;i<n1;i++){ 38 a[i] = StdRandom.uniform(100); 39 } 40 for(int i=0;i<n2;i++){ 41 b[i] = StdRandom.uniform(100); 42 } 43 Arrays.sort(a); 44 Arrays.sort(b); 45 System.out.println("a="+Arrays.toString(a)); 46 System.out.println("b="+Arrays.toString(b)); 47 int[] c = new int[n]; 48 int i = 0; 49 int j = 0; 50 int l = 0; 51 while(l<n){ 52 if(i>=n1) c[l++] = b[j++]; 53 else if(j>=n2) c[l++] = a[i++]; 54 else{ 55 if(a[i] <= b[j]) 56 c[l++] = a[i++]; 57 else 58 c[l++] = b[j++]; 59 } 60 61 } 62 System.out.println("c="+Arrays.toString(c)); 63 64 int k =StdRandom.uniform(1,n); 65 int largestK = find(a,0,n1-1,b,0,n2-1,k); 66 System.out.println("第"+k+"大元素是："+largestK); 67 } 68 }