LeetCode 筆記 - 4. Median of Two Sorted Arrays

題目在此 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

也許你也會想看看