forked from liuyubobobo/Play-Leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathmain.cpp
80 lines (64 loc) · 2.46 KB
/
main.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/// Source : https://leetcode.com/problems/median-of-two-sorted-arrays/
/// Author : liuyubobobo
/// Time : 2019-06-13
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
/// Binary Search
/// Time Complexity: O(log(min(n, m)))
/// Space Complexity: O(1)
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
if(nums1.size() > nums2.size()) swap(nums1, nums2);
int n = nums1.size(), m = nums2.size();
if(n == 0) return m % 2 ? nums2[m / 2] : (nums2[m / 2 - 1] + nums2[m / 2]) / 2.0;
int half = (n + m) / 2;
int l = 0, r = n;
while(l <= r){
int mid = (l + r) / 2;
int i1 = mid, i2 = half - i1;
int leftMax = i1 == 0 ? nums2[i2 - 1] :
i2 == 0 ? nums1[i1 - 1] : max(nums1[i1 - 1], nums2[i2 - 1]);
int rightMin = i1 == n ? nums2[i2] :
i2 == m ? nums1[i1] : min(nums1[i1], nums2[i2]);
if(leftMax <= rightMin){
if((n + m) % 2 == 1)
return rightMin;
else{
int nums1Left = i1 == 0 ? INT_MIN :
i1 == 1 ? nums1[i1 - 1] : max(nums1[i1 - 1], nums1[i1 - 2]);
int nums1Right = i1 == n ? INT_MAX :
i1 == n - 1 ? nums1[i1] : min(nums1[i1], nums1[i1 + 1]);
int nums2Left = i2 == 0 ? INT_MIN :
i2 == 1 ? nums2[i2 - 1] : max(nums2[i2 - 1], nums2[i2 - 2]);
int nums2Right = i2 == m ? INT_MAX :
i2 == m - 1 ? nums2[i2] : min(nums2[i2], nums2[i2 + 1]);
return (max(nums1Left, nums2Left) + min(nums1Right, nums2Right)) / 2.0;
}
}
else if(nums1[i1] == rightMin)
l = mid + 1;
else
r = mid - 1;
}
assert(false);
return -1;
}
};
int main() {
vector<int> nums11 = {1, 3};
vector<int> nums12 = {2};
cout << Solution().findMedianSortedArrays(nums11, nums12) << endl;
// 2
vector<int> nums21 = {1, 2};
vector<int> nums22 = {3, 4};
cout << Solution().findMedianSortedArrays(nums21, nums22) << endl;
// 2.5
vector<int> nums31 = {};
vector<int> nums32 = {1};
cout << Solution().findMedianSortedArrays(nums31, nums32) << endl;
// 1
return 0;
}