leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0004.cpp (1183B)

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