leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0004.cpp (1183B)

      1 class Solution {
      2   public:
      3     double findMedianSortedArrays(const vector<int> &nums1, const vector<int> &nums2) {
      4         const int n1 = nums1.size(), n2 = nums2.size(), n = n1 + n2;
      5         if (n % 2)
      6             return binary(nums1, nums2, n / 2, 0, n1 - 1, 0, n2 - 1);
      7         else
      8             return (binary(nums1, nums2, n / 2 - 1, 0, n1 - 1, 0, n2 - 1) +
      9                     binary(nums1, nums2, n / 2, 0, n1 - 1, 0, n2 - 1)) /
     10                    2.0;
     11     }
     12 
     13     double binary(const vector<int> &nums1, const vector<int> &nums2, int k, int s1, int e1, int s2, int e2) {
     14         if (s1 > e1) return nums2[k - s1];
     15         if (s2 > e2) return nums1[k - s2];
     16 
     17         const int m1 = s1 + (e1 - s1) / 2;
     18         const int m2 = s2 + (e2 - s2) / 2;
     19 
     20         if (m1 + m2 < k) {
     21             return nums1[m1] > nums2[m2] ? binary(nums1, nums2, k, s1, e1, m2 + 1, e2)
     22                                          : binary(nums1, nums2, k, m1 + 1, e1, s2, e2);
     23         } else {
     24             return nums1[m1] > nums2[m2] ? binary(nums1, nums2, k, s1, m1 - 1, s2, e2)
     25                                          : binary(nums1, nums2, k, s1, e1, s2, e2 - 1);
     26         }
     27         return -1;
     28     }
     29 };