LeetCode(4) － Median of Two Sorted Arrays

　　题目要求很简单，就是给你两个已经排好序的数组nums1（长度为m）和nums2（长度为n），找出他们的中间值。返回值类型double是因为如果数字个数是偶数个，就要返回中间两个数的平均值。这题最简单的方法就是通过两个指针分别从nums1和nums2的头一直移动，直到走到nums1和nums2的中值位置为止。整个过程耗时大概是O((m+n) / 2)。但是题目附带需要用O(log(m+n))的时间完成，所以上述方法就不能用了。能用到O(log(m+n))的方法在leetcode的算法题里面没有几个，二分法是最常见的一种。其实一般来说，array，sorted，寻找某个数，看到这些关键词，就可以考虑（不是一定）使用二分法来做。问题是，这一题怎么使用二分法？

　　其实这一个问题可以延伸至在两个数组之间寻找第kth个元素，只是现在k = (m+n) / 2。为了方便理解，我举个例子，假设有两个数组，分别是:

nums1 = [1,4,5,6,8,10]

nums2 = [1,2,4,7,9,11]

　　因为我要找到第k个数，所以我把nums1从k/2处划分两部分，把nums2也从k/2处划分两部分，此题中，k/2 = (12 / 2) / 2 = 3，故index 应该是k/2 - 1处：

1 4 5 ｜ 6 8 10

1 2 4 ｜ 7 9 11

　　这时候，比较nums1和nums2在index处的大小，发现nums2[index] < nums1[index]，这个结果我们可以保证，第k个数一定不在1，2，4里面（为什么？请读者自己证明），所以我们可以大胆从nums2里面把1，2，4给删除。这样，就把在两个数组间寻找第k个元素转变为寻找第(k - (index+1))个元素，继续进入递归或者迭代，直到找到那个第k个元素为止。那什么时候算找到呢？有三种情况：

当其中一个数组被删光（假设为nums1)，则返回的就是nums2[k'-1]（这个k'是迭代多次后的k'）。
当k=1的时候，那么，只需要找nums1[0]和nums2[0]中的较小者就可以。
当nums1[k/2 - 1] ＝ nums2[k/2 - 1]的时候，则这个数就是所要寻找的第k个数。

　　当然，如果nums1的长度小于k/2怎么办？那么就用nums1[m-1]和nums2[k - m - 1]比较，比较后的处理也是一样的。代码如下：

 1 //总体思路：把寻找两个sorted数组的中值转变为寻找两个sorted数组的第k大元素。
 2 public class Solution {
 3     public double findMedianSortedArrays(int[] nums1, int[] nums2) {
 4         int total = nums1.length + nums2.length;
 5         //元素个数为基数的时候
 6         if (total % 2 != 0) {
 7             return (double)findKth(nums1,nums2,total / 2 + 1);
 8         }
 9         //元素个数为偶数的时候
10         else {
11             return (findKth(nums1,nums2,total/2) + 
12                     findKth(nums1,nums2,total/2 + 1)) / 2.0;
13         }
14     }
15     
16     private int findKth(int[] nums1, int[] nums2, int k) {
17         //默认nums1的长度小于num2的长度，省去很多不必要的判断。
18         if (nums1.length > nums2.length) return findKth(nums2,nums1,k);
19         if (nums1.length == 0) return nums2[k-1];
20         if (k == 1) return Math.min(nums1[0],nums2[0]);
21         
22         //把K分成两部分。如果nums1.length < k/2,则取k/2个数，否则取nums1.length个数；
23         int index1 = Math.min(k/2,nums1.length);
24         //nums2里的前k-index1个数。
25         int index2 = k - index1;
26         //-1是因为index从0开始，第index1个数就是index1 - 1;
27         //当num1 < num2时，去除掉nums1里包括index1-1之前的所有数(index1个)。
28         if (nums1[index1 - 1] < nums2[index2 - 1]) {
29             int[] temp1 = new int[nums1.length - index1];
30             System.arraycopy(nums1,index1,temp1,0,nums1.length - index1);
31             //更新k值，进入下个递归。
32             return findKth(temp1,nums2,k-index1);
33         }
34         //情况与上面相反。
35         else if (nums1[index1 - 1] > nums2[index2 - 1]) {
36             int[] temp2 = new int[nums2.length - index2];
37             System.arraycopy(nums2,index2,temp2,0,nums2.length - index2);
38             return findKth(nums1,temp2,k - index2);
39         }
40         //两者相同，说明找到了k值。
41         else {
42             return nums1[index1 - 1];
43         }
44     }
45 }

　　当然，代码还可以继续优化，例如加两个变量，可以直接在nums1和nums2上递归而不需要重新建一个数组，这样就能节省不少空间和时间，但是总体的思路是一样的。