leetcode_004 Median of Two Sorted Arrays

題目分析：

• 求兩個有序數組的中位數。要求時間複雜度為O(log(n+m)

解題思路：

• 方法一：合并排序實作

  1）将兩個有序序列比分複制到同一個向量中

  2）對複制後的向量進行排序

  3）最後針對排序後的去中間的數輸出即可。

  注意：此種方法雖然通過了，但是時間複雜度不是O(log(n+m))

• 方法二：轉換為找第k小的數，遞歸實作

  1）如果A或者B為空，直接傳回B[k-1]或者A[k-1]；

  2）如果k為1，傳回A[0]和B[0]中較小值；

  3）如果A[k/2-1]等于B[k/2-1]，傳回其中一個值即可；

  4）如果A[k/2-1]小于B[k/2-1]，則查找範圍去除A[0]到A[k/2-1]資料，同時更新k的值繼續遞歸計算；

  5）如果A[k/2-1]大于B[k/2-1]，則查找範圍去除B[0]到B[k/2-1]資料，同時更新k的值繼續遞歸計算即可。

• 實作程式

  方法一：合并排序實作

  class Solution
  {
      public:
      double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
      {
          int m = nums1.size();
          int n = nums2.size();
          vector<int> sum;
          // 複制nums1到數組中 
          for(int i=0; i<m; i++)
          {
              sum.push_back(nums1[i]);
          }
          // 複制nums2到數組中 
          for(int i=0; i<n; i++)
          {
              sum.push_back(nums2[i]);
          }
          // 對合并的數組進行排序 
          sort(sum.begin(), sum.end());
          // 傳回中位數 
          return (m+n)%2 ? (double)sum.at((m+n)/2) : (sum.at((m+n-1)/2) + sum.at((m+n)/2))/2.0;
      }
  };
             

  方法二：轉換為找第k小的數，遞歸實作

  class Solution
  {
      public:
          double dfs(vector<int> &nums1, int i, vector<int> &nums2, int j, int k)
          {
              // 當nums1為空的情況 
              if (nums1.size() == i)
                  return nums2[j + k - 1];
              // 當nums2為空的情況 
              if (nums2.size() == j)
                  return nums1[i + k - 1]; 
              // 當k = 1的情況 
              if (k == 1)
                  return min(nums1[i], nums2[j]);
              // 計算nums1和nums2的待查找長度 
              int len1 = nums1.size() - i;
              int len2 = nums2.size() - j;
              // 如果nums1待查找長度大于nums2待查找長度，交換 
              if (len1 > len2)
                  return dfs(nums2, j, nums1, i, k);
              // 計算nums1和nums2待查找長度的中間值位置 
              int temp = nums1.size();
              int mid1 = min(i + k / 2, temp);
              int mid2 = j + k - (mid1 - i);
              // 判斷nums1和nums2待查找長度中間值大小
              // 當nums1待查找的中間值小于nums2待查找的中間值，則移除nums1的前一半資料，進行遞歸查找 
              if (nums1[mid1 - 1] < nums2[mid2 - 1])
                  return dfs(nums1, mid1, nums2, j, k - mid1 + i);
              // 當nums2待查找的中間值小于nums1待查找的中間值，則移除nums2的前一半資料，進行遞歸查找 
              else if (nums1[mid1 - 1] > nums2[mid2 - 1])
                  return dfs(nums1, i, nums2, mid2, k - mid2 + j);
              // 當nums1和nums2待查找的中間值相等，則直接傳回其中的一個中間值即為結果 
              else 
                  return nums1[mid1 - 1];
          }
          double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
          {
              int m=nums1.size();
              int n=nums2.size();
              int total = m + n;
              // 當待查資料為奇數，傳回中間值 
              if (total % 2 == 1)
                  return dfs(nums1, 0, nums2, 0, total / 2 + 1);
              // 當待查資料為偶數，傳回兩個中間值的和的一半 
              else
                  return (dfs(nums1, 0, nums2, 0, total / 2) +
                          dfs(nums1, 0, nums2, 0, total / 2 + 1)) / 2;
          }
      };