題目在此 4. Median of Two Sorted Arrays
給定兩個 Sorting 過的數列，請合併後計算出 中位數
解題思維
沒什麼特別的，就是合併之後計算 中位數
有一個小技巧是只需要合併到計算 中位數 需要的長度即可
Time complexity: O(n)
程式碼
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
| class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
merged_array = []
merged_length = len(nums1) + len(nums2)
median_index = int((merged_length) / 2 )
while len(merged_array) <= median_index:
if nums1 and nums2:
if nums1[0] < nums2[0]:
current_num = nums1.pop(0)
else:
current_num = nums2.pop(0)
elif nums1:
current_num = nums1.pop(0)
else:
current_num = nums2.pop(0)
merged_array.append(current_num)
if merged_length % 2 == 1:
return merged_array[median_index]
value_0 = merged_array[median_index]
value_1 = merged_array[median_index - 1]
return (value_0 + value_1) / 2
|
相關文章