Algorithm
本周选择的算法题是：Kth Largest Element in an Array
规则如下：
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Note: You may assume k is always valid, 1 ≤ k ≤ array’s length.
Solution
方法一：基于快排的分区查找
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
start, end = 0, len(nums) - 1
target = len(nums) - k # 将问题从“找第k大”变成“找第x小”
while True:
pivot_index = self.partition(nums, start, end)
if pivot_index == target:
return nums[pivot_index]
elif pivot_index < target:
start = pivot_index + 1
else:
end = pivot_index - 1
return -1
def partition(self, nums: List[int], start: int, end: int) -> int:
pivot = nums[start]
pivot_index = start
for i in range(start+1, end+1):
if nums[i] < pivot:
pivot_index += 1
nums[pivot_index], nums[i] = nums[i], nums[pivot_index]
nums[pivot_index], nums[start] = nums[start], nums[pivot_index]
return pivot_index
方法二：基于堆排序
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
def down_adjust(index: int, length: int):
temp = nums[index]
child_index = index * 2 + 1
while child_index < length:
if child_index + 1 < length and nums[child_index + 1] > nums[child_index]:
child_index += 1
if temp > nums[child_index]:
break
nums[child_index], nums[index] = nums[index], nums[child_index]
index = child_index
child_index = index * 2 + 1
def heapify(max_len: int) -> List[int]: # 建堆
for index in range((max_len - 2) // 2, -1, -1):
down_adjust(index, max_len)
return nums
heap = heapify(len(nums))
for i in range(k-1):
max_len = len(nums)-i-1
nums[0] = nums[max_len]
down_adjust(0, max_len)
return nums[0]
Review
Benefits of using throwing functions (try) - Swift’s most underrated feature?
Swift 原生 try-throw 语句相比 Result 的优势有：
- 逻辑更清晰、简洁
- 更容易做单元测试和代码覆盖率测试
- 接口对使用者更友好，只处理自己关心的错误类型
- 更安全，强制使用者对潜在的异常做出回应
- 更容易维护和修改
Tip
UIGraphicsImageRender 相比 UIGrahpicsBeginImageContext 能极大降低内存使用，因为 UIGraphicsImageRender 针对单色 monochrome 做了优化，这种场景下每像素只使用1个字节，而不是4个。
这个优化也被应用在了 UILabel 上：UILabel 的内存开销比你认为的要多
Share
一篇关于高性能优化的实践指导，传送门