3 solutions: use a helper getkth, and use binary search


  • 1
    Y

    1 & 2. O(log(m+n))

    class Solution {
    public:
      double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size(), k = m+n-1 >> 1;
        if (m+n & 1) return getkth(nums1, nums2, k);
        return (getkth(nums1, nums2, k) + getkth(nums1, nums2, k+1)) * 0.5;
      }
    private:
      int getkth(vector<int>& a, vector<int>& b, int k) {  // 0 index
        int m = a.size(), n = b.size(), i = 0, j = 0;
        while (k) {
          int p = k-1>>1;
          if (i+p >= m || j+p < n && a[i+p] > b[j+p])
            j += p+1;
          else
            i += p+1;
          k -= p+1;
        }
        return i >= m || j < n && a[i] > b[j] ? b[j] : a[i];
      }
    };
    
    //another way of writing getkth
    int getkth(vector<int>& a, vector<int>& b, int k) { // 0 index
      int m = a.size(), n = b.size(), i = 0, j = 0;
      while (m && n && k) {
        int p = k-1>>1, ii = min(m-1, p), jj = min(n-1, p);
        if (a[i+ii] > b[j+jj])
          j += jj+1, n -= jj+1, k -= jj+1;
        else
          i += ii+1, m -= ii+1, k -= ii+1;
      }
      if (!m) return b[j+k];
      if (!n) return a[i+k];
      return min(a[i], b[j]);
    }
    
    1. O(log(min(m,n))) binary search on smaller array. I tried write a seperate getkth helper at first, then there're just too many corner cases to deal with such that writing a generalized version seems tedious.
    class Solution {
    public:
      double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        if (m > n) return findMedianSortedArrays(nums2, nums1);
        bool odd = m+n & 1;
        int k = m+n-1>>1;
        if (!m)
          return odd ? nums2[k] : 0.5*nums2[k] + 0.5*nums2[k+1];
        if (nums1[0] >= nums2[k]) {
          if (odd) return nums2[k];
          return 0.5*nums2[k] + 0.5*(k==n-1 || nums2[k+1]>nums1[0] ? nums1[0] : nums2[k+1]);
        }
        if (k >= m) {
          if (nums2[k-m] >= nums1[m-1])
            return odd ? nums2[k-m] : 0.5*nums2[k-m] + 0.5*nums2[k-m+1];
          else if (nums1[m-1] <= nums2[k-m+1])
            return odd ? nums1[m-1] : 0.5*nums1[m-1] + 0.5*nums2[k-m+1];
        } else if (nums1[m-1] <= nums2[0])
          return odd ? nums1[m-1] : 0.5*nums1[m-1] + 0.5*nums2[0];
    
        int l = 0, h = m-1;
        while (l <= h) {
          int i = l+h >> 1, j = k-i-1;
          if (nums1[i] < nums2[j]) {
            if (nums1[i+1] >= nums2[j])
              return odd ? nums2[j] : 0.5*nums2[j] + 0.5*min(nums1[i+1], nums2[j+1]);
            l = i+1;
          } else {
            if (nums2[j+1] >= nums1[i])
              return odd ? nums1[i] : 0.5*nums1[i] + 0.5*min(nums2[j+1], nums1[i+1]);
            h = i-1;
          }
        }
        return -1;
      }
    };
    

  • 0
    D

    hey yijiexu3,
    I am not able to understand this code

    int getkth(vector<int>& a, vector<int>& b, int k) {  // 0 index
        int m = a.size(), n = b.size(), i = 0, j = 0;
        while (k) {
          int p = k-1>>1;//what's the idea here to choose p like that ?
          if (i+p >= m || j+p < n && a[i+p] > b[j+p])
            j += p+1;//since a[i+p]>b[j+p] , we are increasing b's next comparison?
          else
            i += p+1;
          k -= p+1;
        }
        return i >= m || j < n && a[i] > b[j] ? b[j] : a[i];
      }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.