ARTS挑战-第四周

什么是ARTS?

1.Algorithm:每周至少做一个 leetcode 的算法题
2.Review:阅读并点评至少一篇英文技术文章
3.Tip:学习至少一个技术技巧
4.Share:分享一篇有观点和思考的技术文章

Algorithm

这道题与之前的题目不同,第一次出现了限制时间复杂度:O(log (m+n)),并且还是查找中位数,自然就想到了二分法。但是这是两个有序数组查找中位数,因此就很难了。。

Q:

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:

1
2
3
4
nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

1
2
3
4
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

A:

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
class Solution {
func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
let m = nums1.count
let n = nums2.count

let left = (m + n + 1) / 2
let right = (m + n + 2) / 2
return Double(findK(nums1: nums1, nums2: nums2, k: (m + n + 1) / 2) + findK(nums1: nums1, nums2: nums2, k: (m + n + 2) / 2)) / 2.0
}

func findK(nums1: [Int], nums2: [Int], k: Int) -> Int {
let m: Int = nums1.count
let n: Int = nums2.count

if (nums1.isEmpty) {
return nums2[k - 1]
}

if (nums2.isEmpty) {
return nums1[k - 1]
}

if (k == 1) {
return min(nums1[0], nums2[0])
}

let i = min(m, k / 2)
let j = min(n, k / 2)
if (nums1[i - 1] > nums2[j - 1]) {
return findK(nums1: nums1, nums2: Array(nums2[j..<n]), k: k - j)
} else {
return findK(nums1: Array(nums1[i..<m]), nums2: nums2, k: k - i)
}
}
}

Review

Coordinators
这篇文章标题很简洁,就是 Coordinators, 通篇也就讲了一件事情,如何写一个协调器,这里边使用了MVVM的思想,代码很简洁。
最后顺便学习个英语,有句话很有意思: Remember that you don't need a bazooka to kill a fly.,意思是:别用高射炮打蚊子。

Tip

平时我们处理optional类型的时候需要一大堆比较繁琐的解包,这里有一另一种方式:
使用抛出异常的方式来处理nil的情况。

1
2
3
4
5
6
7
8
9
10
11
12
extension Optional {
func orThrow(_ errorExpression: @autoclosure () -> Error) throws -> Wrapped {
switch self {
case .some(let value):
return value
case .none:
throw errorExpression()
}
}
}

let file = try loadFile(at: path).orThrow(MissingFileError())

Share

这周分享一篇对于响应式编程的思考 为什么需要Reactive Programming?