Algorithm
本周选择的算法题是：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
Solution
这题的重点在于 O(log (m+n))，既是限制，也是提示。
先忽略看常规解法：
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
def _merge():
nums = []
nums1_begin, nums2_begin = 0, 0
while nums1_begin < len(nums1) and nums2_begin < len(nums2):
if nums1[nums1_begin] < nums2[nums2_begin]:
nums.append(nums1[nums1_begin])
nums1_begin += 1
else:
nums.append(nums2[nums2_begin])
nums2_begin += 1
while nums1_begin < len(nums1):
nums.append(nums1[nums1_begin])
nums1_begin += 1
while nums2_begin < len(nums2):
nums.append(nums2[nums2_begin])
nums2_begin += 1
return nums
nums = _merge()
if len(nums) % 2 == 0:
return (nums[len(nums)//2] + nums[len(nums)//2-1]) / 2
else:
return nums[len(nums)//2]
这个解法用到了归并排序的思想，将两个源数据二路合并成一个排序数据，然后取中位数。
其实不需要做完整的排序，只需要记录中位数的值即可，这样可以降低空间复杂度：
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
nums1_begin, nums2_begin, half_len = 0, 0, (len(nums1) + len(nums2)) // 2
left, right = 0, 0
while half_len >= 0:
half_len -= 1
left = right
if nums1_begin < len(nums1) and (nums2_begin >= len(nums2) or nums1[nums1_begin] < nums2[nums2_begin]):
right = nums1[nums1_begin]
nums1_begin += 1
else:
right = nums2[nums2_begin]
nums2_begin += 1
if (len(nums1) + len(nums2)) % 2 == 0:
return (left + right) / 2
else:
return right
上述两个解法都不符合时间复杂度的要求，做完只当是热热身，吃透这道题。
在评论区看到的解法，通过寻找第 k 小的数字巧妙的将问题分解：
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
def _kth(nums1_begin, nums2_begin, k) -> int:
len1 = len(nums1) - nums1_begin
len2 = len(nums2) - nums2_begin
if len1 == 0: return nums2[nums2_begin + k - 1]
if len2 == 0: return nums1[nums1_begin + k - 1]
if k == 1: return min(nums1[nums1_begin], nums2[nums2_begin])
i = nums1_begin + min(k // 2, len1) - 1
j = nums2_begin + min(k // 2, len2) - 1
if nums1[i] < nums2[j]:
return _kth(i + 1, nums2_begin, k - (i - nums1_begin + 1))
else:
return _kth(nums1_begin, j + 1, k - (j - nums2_begin + 1))
total_len = len(nums1) + len(nums2)
if total_len % 2 == 0:
return (_kth(0, 0, total_len // 2) + _kth(0, 0, total_len // 2 + 1)) / 2
else:
return _kth(0, 0, total_len // 2 + 1)
官方解法，对两个数组进行二分，边界条件很多：
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
m, n = len(nums1), len(nums2)
if m > n: return self.findMedianSortedArrays(nums2, nums1)
imin, imax = 0, m
while imin <= imax:
i = (imin + imax) // 2
j = (m + n + 1) // 2 - i
if i < m and nums2[j-1] > nums1[i]: # i 太小
imin = i + 1
elif i > 0 and nums1[i-1] > nums2[j]: # i 太大
imax = i - 1
else: # i 合适
if i == 0: max_left_num = nums2[j-1]
elif j == 0: max_left_num = nums1[i-1]
else: max_left_num = max(nums1[i-1], nums2[j-1])
if (m + n) % 2 == 0:
if i == m: min_right_num = nums2[j]
elif j == n: min_right_num = nums1[i]
else: min_right_num = min(nums1[i], nums2[j])
return (max_left_num + min_right_num) / 2
else:
return max_left_num
Review
Swift globals and static members are atomic and lazily computed
从这篇文章中了解到 Swift 相比 OC 做的一些优化。
Swift 的全局或静态成员是原子和懒加载的，它们的初始化方法是通过 dispatch_once 包裹的，除此之外，如果是 let 还有线程安全的作用，由于 let 本身代表了不可变，因此这也是合理的操作。
Tip
zsh-autosuggestions 插件真香！
Share
一篇关于 《软件架构设计》 的读后感，传送门