题目

4. 寻找两个有序数组的中位数

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

解题思路

1.由于本身有序，将两个表分别遍历一遍排序得到一个新的有序表
2.分奇偶讨论，返回中位数结果

代码：

  1. class Solution {
  2. public:
  3.     double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
  4.         int sum = nums1.size() + nums2.size();
  5.         vector<int> nums(sum);
  6.         int i = 0;
  7.         int j = 0;
  8.         int k = 0;
  9.         for(; k < sum;){
  10.             if(j >= nums2.size() || (i < nums1.size() && nums1[i] <= nums2[j]) ){
  11.                 nums[k++] = nums1[i++];
  13.             }
  14.             else{
  15.                 nums[k++] = nums2[j++];
  16.             }
  17.         }
  18.         if(sum % 2 == 0){
  19.             return (nums[sum/2] + nums[sum/2 - 1])/2.0;
  20.         }
  21.         else{
  22.             return nums[(sum - 1) / 2];
  23.         }
  24.     }
  25. };

思考：

1.有关vector的使用问题，我在代码中有两个地方涉及到vector问题：
（1）if（num1s[i] < nums2[j]）可能会出现i或者j越界，解决方式：将i，j的越界条件提前进行判断，如果不满足根据&&和||的性质，将不会执行该代码；
（2）定义nums时，开始是使用vector nums，报错：reference binding to null pointer of type ‘const value_type’，对于该错误的修正可以参考下面的博客：https://blog.csdn.net/sunprice/article/details/82928596；解决的方式是给nums确定size（），定义为vector nums(sum)即可。

2.官网提交，最快有0s的，也有4s的，一个点在于对于nums1和nums2数组的size()进行了过多次判断，可以通过return的方式使得判断size的代码只需要执行一次。

3.0s代码如下，来自官网：

  1. class Solution {
  2. public:
  3.     double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
  4.         int m = nums1.size();
  5.         int n = nums2.size();
  6.         if(m > n){
  7.             return findMedianSortedArrays(nums2, nums1);
  8.         }
  9.         int halflen = (m + n + 1) / 2;
  10.         int mn = 0, mx = m;
  11.         int i = (mn + mx) >> 1, j = halflen - i;
  12.         double maxleft, minright;
  13.         while(mn <= mx){
  14.             i = (mn + mx) >> 1;
  15.             j = halflen - i;
  16.             if(i < mx && nums2[j-1] > nums1[i]){
  17.                 mn = i + 1;
  18.             } else if(i > mn && nums1[i-1] > nums2[j]){
  19.                 mx = i - 1;
  20.             } else {
  21.                 // 分别求出maxleft和minright
  22.                 if(i == 0){
  23.                     // left part中不存在A
  24.                     maxleft = nums2[j-1];
  25.                 } else if (j == 0){
  26.                     maxleft = nums1[i-1];
  27.                 } else {
  28.                     maxleft = max(nums1[i-1], nums2[j-1]);
  29.                 }
  30.                 if((m + n) % 2)
  31.                     return maxleft;
  32.                 if(i == m){
  33.                     minright = nums2[j];
  34.                 } else if (j == n){
  35.                     minright = nums1[i];
  36.                 } else {
  37.                     minright = min(nums1[i], nums2[j]);
  38.                 }
  39.                 return (minright + maxleft) / 2;
  40.             }
  41.         }
  42.         return 0;
  43.     }
  44. };