Created
April 25, 2019 09:17
-
-
Save adamkorg/ffba283f298e7c2c2b748acb49ccc9f1 to your computer and use it in GitHub Desktop.
Leetcode median of two sorted arrays problem
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <vector> | |
using namespace std; | |
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { | |
int size1 = nums1.size(); | |
int size2 = nums2.size(); | |
if (size1 < size2) //if one array is smaller then we want smaller in nums2 | |
return findMedianSortedArrays(nums2, nums1); | |
if (size2 == 0) //single list | |
return (double(nums1[(size1-1)/2])+nums1[size1/2])/2; | |
int start1 = 0, start2 = 0; | |
int len1 = size1, len2 = size2; | |
bool beyond_start1=false, beyond_start2=false, beyond_end1=false, beyond_end2=false; | |
while (true) { | |
int L1 = (beyond_start1) ? INT_MIN : nums1[start1 + ((len1-1)/2)]; | |
int L2 = (beyond_start2) ? INT_MIN : nums2[start2 + ((len2-1)/2)]; | |
int R1 = (beyond_end1) ? INT_MAX : nums1[start1 + (len1/2)]; | |
int R2 = (beyond_end2) ? INT_MAX : nums2[start2 + (len2/2)]; | |
if (L1 > R2) { //partition list 2 window to use 2nd half (right half) | |
if (len2==1) { //beyond end of list 2 edge case | |
if (start2<size2-1) | |
len2++; | |
else | |
beyond_end2 = true; | |
if (len1==1) { //and beyond start of list1 edge case | |
if (start1>0) { | |
len1++; | |
start1--; | |
} | |
else | |
beyond_start1 = true; | |
} | |
else | |
len1--; | |
} | |
else { | |
int new_len2 = (len2/2); | |
start2 += ((len2+1)/2); | |
int num_discarded = len2 - new_len2; | |
len2 = new_len2; | |
//also discard num_discarded from right side of list 1 window | |
len1 = len1 - num_discarded; | |
} | |
} | |
else if (R1 < L2) { //partition list 2 window to use 1st half (left half) | |
if (len2==1) { //before start of list 2 edge case | |
if (start2>0) { | |
start2--; | |
len2++; | |
} | |
else | |
beyond_start2 = true; | |
if (len1==1) { //beyond end of list 1 edge case | |
if (start1<size1-1) | |
len1++; | |
else | |
beyond_end1 = true; | |
} | |
else { | |
start1++; | |
len1--; | |
} | |
} | |
else { | |
int new_len2 = (len2/2); | |
int num_discarded = len2 - new_len2; | |
len2 = new_len2; | |
//also discard num_discarded from left side of list1 window | |
start1 += num_discarded; | |
len1 -= num_discarded; | |
} | |
} | |
else { | |
return ((double(max(L1,L2))+min(R1,R2))/2); | |
} | |
} | |
return -1; | |
} | |
int main() { | |
cout << "findMedianSortedArrays({3,6,8,11,15,18},{1,2,4,7}) = "; | |
vector<int> nums1 = {3,6,8,11,15,18}; | |
vector<int> nums2 = {1,2,4,7}; | |
cout << findMedianSortedArrays(nums1, nums2) << endl; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment