4.jpeg

    代码 :

    1. class Solution {
    2. public:
    3.     double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    4.         int k = nums1.size() + nums2.size();
    6.         if(k%2 == 0){
    7.             int left =  findKth(nums1, 0, nums2, 0, k/2);
    8.             int right = findKth(nums1, 0, nums2, 0, k/2+1);
    9.             return (left+right) / 2.0;
    10.         }
    11.         else{
    12.             return findKth(nums1, 0, nums2, 0, k/2+1);
    13.         }
    14.     }
    16.     // 从第 i&j元素 开始找第k个元素
    17.     // e.g 从A数组m下标找第k个数 A[m+k-1] => k=1 return A[m]
    18.     int findKth(vector<int>& nums1, int i, vector<int>& nums2, int j, int k){
    19.         // 始终保持短数组在前
    20.         if(nums1.size()-i > nums2.size()-j) 
    21.             return findKth(nums2, j, nums1, i, k);
    23.         // 下一个元素为目标元素 -> 递归终点
    24.         if(k==1) {
    25.             if(nums1.size() == i) return nums2[j];
    26.             else return min(nums1[i], nums2[j]);
    27.         }
    29.         // case1 : 短数组长度小于k/2 
    30.         // 第一个数组为空, 则在第二个数组中找第k个数 
    31.         if(nums1.size() == i)
    32.             return nums2[j+k-1];
    34.         // case2 : si sj =>记录A[k/2] B[k/2] 下标
    35.         int si = min(i+k/2, (int)nums1.size())-1, sj = j+k/2-1;
    36.         if(nums1[si] > nums2[sj]) 
    37.             return findKth(nums1, i, nums2, sj+1, k-(sj+1-j));
    38.         else // (nums1[si-1] < nums2[sj-1]) 
    39.             return findKth(nums1, si+1, nums2, j, k-(si+1-i));
    40.     }
    41. };