LeetCode4 Median of Two Sorted Arrays

题目：

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). (Hard)

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5


分析：

利用寻找第K个元素的辅助函数。
二分搜索的思想，每次尽量去掉数组中的一部分元素(一半左右)；
一次取K个元素出来，nums1中取 K/2个(不够就全都取出)， nums2中取 K - K/2(或nums1.size()),
判断取出的两个数组元素中的末位谁大谁小；
如果nums1[p1] < nums2[p2]，说明nums1取少了，nums2取多了，第K个元素应该在nums1的后半部分或nums2的前半部分；
如果nums1[p1] > nums2[p2], 说明nums2取少了，nums1取多了，第K个元素应该在nums2的后半部分或nums1的前半部分；
递归求解即可 。边界条件是nums1或nums2为空或K为1；

注：题目思路不是很难想到，但是处理细节有很多容易错的地方。
1.首先应确定Kth是第K个元素，对应下标应该为K-1
2.数组下标，取1/2位置时对应的哪个位置等等要注意，可以采用走样例的方式保证不出错。
3.采用了两种实现方法，一种是拷贝vector，要传参的时候注意左闭右开；
　　　　　　　　　　  另一种是不拷贝vector，多传两个起始位置start，注意每次取元素操作时不能忘记start
  第二个效率稍高，但编码中可能出错的地方也多一点。

代码1：

 1 class Solution {
 2 private:
 3     double findKth(vector<int>& nums1, vector<int>& nums2, int K) { //第K个，对应下标K-1
 4         if (nums1.size() > nums2.size()) {
 5             return findKth(nums2,nums1,K);
 6         }
 7         if (nums1.size() == 0) {
 8             return nums2[K-1];
 9         }
10         if (nums2.size() == 0) {
11             return nums1[K-1];
12         }
13         if (K == 1) {
14             return min(nums1[0], nums2[0]);
15         }
16         int s = nums1.size();
17         int p1 = min( K / 2, s);
18         int p2 = K - p1;
19         if (nums1[p1 - 1] < nums2[p2 - 1]) { //说明nums1取少了，kth在nums1后半段或nums2前半段
20             vector<int> n1(nums1.begin() + p1, nums1.end());
21             vector<int> n2(nums2.begin(), nums2.begin() + p2);
22             return findKth(n1, n2, K - p1);
23         }
24         else {
25             vector<int> n3(nums1.begin(), nums1.begin() + p1);
26             vector<int> n4(nums2.begin() + p2, nums2.end());
27             return findKth(n3, n4, K - p2);
28         }
29      }
30 public:
31     double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
32         int s1 = nums1.size(), s2 = nums2.size();
33         int mid = (s1 + s2) / 2;
34         if ( (s1 + s2) % 2 == 0 ) {
35             return (findKth(nums1, nums2, mid) + findKth(nums1, nums2, mid + 1)) / 2.0; 
36         } 
37         else {
38             return findKth(nums1, nums2, mid + 1);
39         }
40     }
41 };

代码2：

 1 class Solution {
 2 private:
 3     double findKth(vector<int>& nums1, vector<int>& nums2, int K ,int start1, int start2) { //第K个，对应下标K-1
 4         if (nums1.size() - start1 > nums2.size() - start2) {
 5             return findKth(nums2,nums1,K,start2,start1);
 6         }
 7         if (nums1.size() - start1 == 0) {
 8             return nums2[start2 + K - 1];
 9         }
10         if (nums2.size() - start2 == 0) {
11             return nums1[start1 + K - 1];
12         }
13         if (K == 1) {
14             return min(nums1[start1], nums2[start2]);
15         }
16         int s = nums1.size() - start1;
17         int p1 =  min( K / 2, s);
18         int p2 =  K - p1;
19         if (nums1[start1 + p1 - 1] < nums2[start2 + p2 - 1]) { //说明nums1取少了，kth在nums1后半段或nums2前半段
20             return findKth(nums1, nums2, K - p1, start1 + p1,start2);
21         }
22         else {
23             return findKth(nums1, nums2, K - p2, start1, start2 + p2);
24         }
25      }
26 public:
27     double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
28         int s1 = nums1.size(), s2 = nums2.size();
29         int mid = (s1 + s2) / 2;
30         if ( (s1 + s2) % 2 == 0 ) {
31             return (findKth(nums1, nums2, mid,0,0) + findKth(nums1, nums2, mid + 1,0,0)) / 2.0; 
32         } 
33         else {
34             return findKth(nums1, nums2, mid + 1,0,0);
35         }
36     }
37 };

其他与二分搜索相关的问题可以参考：

http://www.cnblogs.com/wangxiaobao/p/4915853.html