-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path4 Median of Two Sorted Arrays.py
184 lines (149 loc) · 7.49 KB
/
4 Median of Two Sorted Arrays.py
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
def find_med(nums):
num_len = len(nums)
if num_len % 2 == 0:
med = (nums[num_len//2] + float(nums[num_len//2-1]))/2
else:
med = nums[num_len//2]
med_i = max(1, num_len//2)
return med, (med_i-1, med_i)
def find_med_i(nums, left, right):
num_len = right - left
if num_len % 2 == 0:
med = (nums[int(left + num_len//2)] + float(nums[int(left + num_len//2-1)]))/2
else:
med = nums[int(left + num_len//2)]
med_i = max(1, int(left + num_len//2))
return med, (med_i-1, med_i)
if not len(nums1):
return find_med(nums2)[0]
if not len(nums2):
return find_med(nums1)[0]
total_num = (len(nums1) + len(nums2))
if total_num % 2 == 0:
side_num = int(total_num / 2 - 1)
else:
side_num = int(total_num // 2)
left_med, left_med_i = find_med(nums1)
right_med, right_med_i = find_med(nums2)
if left_med == right_med:
return left_med
if total_num <= 6:
return find_med(sorted(nums1 + nums2))[0]
if len(nums1) < 2:
nums1 = sorted(nums1 + nums2[:1])
nums2 = nums2[1:]
elif len(nums2) < 2:
nums2 = sorted(nums2 + nums1[:1])
nums1 = nums1[1:]
min_count = 0
max_count = 0
med_left_A, med_right_A = left_med_i[0], left_med_i[1]
med_left_B, med_right_B = right_med_i[0], right_med_i[1]
left_bound_A, left_bound_B = 0, 0
right_bound_A, right_bound_B = len(nums1), len(nums2)
while min_count < side_num or max_count < side_num:
if (right_bound_A - left_bound_A) + (right_bound_B - left_bound_B) <= 6:
sort_list = sorted(nums1[left_bound_A:right_bound_A] + nums2[left_bound_B:right_bound_B])
min_rest = side_num - min_count
max_rest = side_num - max_count
if not max_rest:
sort_list = sort_list[int(min_rest):]
else:
sort_list = sort_list[int(min_rest):int(-max_rest)]
return find_med(sort_list)[0]
if min_count < side_num and nums1[med_left_A] < nums2[med_left_B] and med_left_A - left_bound_A > 0:
min_rest = side_num - min_count
if min_rest > med_left_A - left_bound_A:
min_count += med_left_A - left_bound_A
left_bound_A = med_left_A
else:
left_bound_A += min_rest
min_count += min_rest
med_left_A, med_right_A = find_med_i(nums1, left_bound_A, right_bound_A)[1]
elif min_count < side_num and nums1[med_left_A] > nums2[med_left_B] and med_left_B - left_bound_B > 0:
min_rest = side_num - min_count
if min_rest > med_left_B - left_bound_B:
min_count += med_left_B - left_bound_B
left_bound_B = med_left_B
else:
left_bound_B += min_rest
min_count += min_rest
med_left_B, med_right_B = find_med_i(nums2, left_bound_B, right_bound_B)[1]
elif max_count < side_num and nums1[med_right_A] > nums2[med_right_B] and right_bound_A - med_right_A > 0:
max_rest = side_num - max_count
if max_rest > right_bound_A - med_right_A:
max_count += right_bound_A - med_right_A
right_bound_A = med_right_A
else:
right_bound_A -= max_rest
max_count += max_rest
med_left_A, med_right_A = find_med_i(nums1, left_bound_A, right_bound_A)[1]
elif max_count < side_num and nums1[med_right_A] < nums2[med_right_B] and right_bound_B - med_right_B > 0:
max_rest = side_num - max_count
if max_rest > right_bound_B - med_right_B:
max_count += right_bound_B - med_right_B
right_bound_B = med_right_B
else:
right_bound_B -= max_rest
max_count += max_rest
med_left_B, med_right_B = find_med_i(nums2, left_bound_B, right_bound_B)[1]
else:
if min_count < side_num and med_left_A - left_bound_A > 0:
min_rest = side_num - min_count
if min_rest > med_left_A - left_bound_A:
min_count += med_left_A - left_bound_A
left_bound_A = med_left_A
else:
left_bound_A += min_rest
min_count += min_rest
med_left_A, med_right_A = find_med_i(nums1, left_bound_A, right_bound_A)[1]
elif min_count < side_num and med_left_B - left_bound_B > 0:
min_rest = side_num - min_count
if min_rest > med_left_B - left_bound_B:
min_count += med_left_B - left_bound_B
left_bound_B = med_left_B
else:
left_bound_B += min_rest
min_count += min_rest
med_left_B, med_right_B = find_med_i(nums2, left_bound_B, right_bound_B)[1]
elif max_count < side_num and right_bound_A - med_right_A > 0:
max_rest = side_num - max_count
if max_rest > right_bound_A - med_right_A:
max_count += right_bound_A - med_right_A
right_bound_A = med_right_A
else:
right_bound_A -= max_rest
max_count += max_rest
med_left_A, med_right_A = find_med_i(nums1, left_bound_A, right_bound_A)[1]
elif max_count < side_num and right_bound_B - med_right_B > 0:
max_rest = side_num - max_count
if max_rest > right_bound_B - med_right_B:
max_count += right_bound_B - med_right_B
right_bound_B = med_right_B
else:
right_bound_B -= max_rest
max_count += max_rest
med_left_B, med_right_B = find_med_i(nums2, left_bound_B, right_bound_B)[1]
obj = Solution()
# print(obj.findMedianSortedArrays([1,3],[2]))
# print(obj.findMedianSortedArrays([1],[2,3]))
# print(obj.findMedianSortedArrays([1,2],[3,4]))
# print(obj.findMedianSortedArrays([2],[1,3,4]))
# print(obj.findMedianSortedArrays([1,2],[1,2,3]))
# print(obj.findMedianSortedArrays([1,1],[1,2]))
# print(obj.findMedianSortedArrays([0,0],[0,0]))
# print(obj.findMedianSortedArrays([1,5],[2,3,4,6]))
# print(obj.findMedianSortedArrays([1],[2,3,4,5,6,7]))
# print(obj.findMedianSortedArrays([6],[1,2,3,4,5,7,8]))
# print(obj.findMedianSortedArrays([1,5],[2,3,4,6,7]))
print(obj.findMedianSortedArrays([1,2,6],[3,4,5,7,8]))
# print(obj.findMedianSortedArrays([1,2,3,4],[-999,-988,12]))
# print(obj.findMedianSortedArrays([1,2,3,4,5,7],[5,6,7,9]))
# print(obj.findMedianSortedArrays([0,0,0,0,0],[-1,0,0,0,0,0,1]))