Problem: Median of Two Sorted Arrays
- There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). You may assume nums1 and nums2 cannot be both empty.
- Example 1: nums1 = [1, 3], nums2 = [2]. The median is 2.0.
- Example 2: nums1 = [1, 2], nums2 = [3, 4]. The median is (2 + 3)/2 = 2.5.
- Example 3: nums1 = [1, 4], nums2 = [2, 3]. The median is (2 + 3)/2 = 2.5.
- Link: https://leetcode.com/problems/median-of-two-sorted-arrays/
Analysis
相关问题1: 寻找一个排好序的数列的中位数(median of one sorted array)
1
2
3
4# 复杂度为O(1)
def Median(nums):
mid = len(nums) // 2
return (nums[mid] + nums[~mid]) / 2相关问题1: 寻找一个未排序的数列的中位数(median of one unsorted array)
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# Brute Force: 排序 + 返回，复杂度为O(nlogn)
def Median(nums):
nums.sort()
mid = len(nums) // 2
return (nums[mid] + nums[~mid]) / 2
# Randomized selection or deterministic selection，只需要定义k为n/2和n/2+1位。复杂度为O(n)
class Search:
def SearchK_deterministic(self, unsorted_nums, k):
"""
:intro: find k-th smallest number in an unsorted and distinct array via deterministic pivot
:param unsorted_nums: unsorted array
:param k: k-th smallest index
:return: k-th smallest number
"""
group = 5
length = len(unsorted_nums) // group
ms = [sorted(unsorted_nums[group * i: group * i + group], reverse=True) for i in range(length)] # 按五个分为一组
ms.append(sorted(unsorted_nums[group * length:], reverse=True)) # 最后一组可以小于5
mm = [s[len(s) // 2] for s in ms if s != []] # 每组的中位数
if len(mm) > 1: # 中位数的中位数作为m，递归实现
m = self.SearchK_deterministic(mm, len(mm) // 2)
else:
m = mm[0]
s1 = []
s2 = []
for num in unsorted_nums:
if num < m:
s1.append(num)
elif num > m:
s2.append(num)
length = len(s1)
if length + 1 == k:
return m
elif length >= k:
return self.SearchK_deterministic(s1, k)
else:
return self.SearchK_deterministic(s2, k - length - 1)
def SearchK_randomized(self, unsorted_nums, k):
"""
:intro: find k-th smallest number in an unsorted and distinct array via randomly pivot
:param unsorted_nums: unsorted array
:param k: k-th smallest index
:return: k-th smallest number
"""
from random import sample
r = sample(range(len(unsorted_nums)), 1)[0] # 随机选一个数
s1 = []
s2 = []
for num in unsorted_nums:
if num < unsorted_nums[r]:
s1.append(num)
elif num > unsorted_nums[r]:
s2.append(num)
length = len(s1)
if length + 1 == k:
return unsorted_nums[r]
elif length >= k:
return self.SearchK_randomized(s1, k)
else:
return self.SearchK_randomized(s2, k - length - 1)
Solutions
1 | # Brute Force: 按序merge两个array，然后直接找出中位数，复杂度为O(n)。这里假设两个数列长度和为n |