Algorithm
本周选择的算法题是：Kth Smallest Element in a Sorted Matrix
规则如下：
Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.
Note that it is the kth smallest element in the sorted order, not the kth distinct element.
Example:
matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
return 13.
Note: You may assume k is always valid, 1 ≤ k ≤ n2.
Solution
堆排序
class Solution:
class HeapSort:
def __init__(self, length):
self.length = length
self.heap = []
def add(self, num):
if len(self.heap) < self.length:
self.heap.append(num)
self._up()
elif num < self.heap[0]:
self.heap[0] = num
self._down()
def _up(self):
index = len(self.heap) - 1
while index > 0:
parent_index = (index + 1) // 2 - 1
if self.heap[parent_index] < self.heap[index]:
self.heap[parent_index], self.heap[index] = self.heap[index], self.heap[parent_index]
index = parent_index
else:
break
def _down(self):
index = 0
child_index = index * 2 + 1
while child_index < self.length:
if child_index + 1 < len(self.heap) and self.heap[child_index + 1] > self.heap[child_index]:
child_index += 1
if self.heap[child_index] <= self.heap[index]:
break
self.heap[child_index], self.heap[index] = self.heap[index], self.heap[child_index]
index = child_index
child_index = index * 2 + 1
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
heap = Solution.HeapSort(k)
for row in matrix:
for num in row:
heap.add(num)
return heap.heap[0]
构建了一个大顶堆；是可以接受的答案，不过没有利用到矩阵有序的特点，还有优化空间
多路归并排序
class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
ptrs, ans = [0] * len(matrix), 0
while k > 0:
k -= 1
row, temp = 0, float('inf')
for i, j in enumerate(ptrs):
if j >= len(matrix): continue
if matrix[i][j] < temp:
temp, row = matrix[i][j], i
ans = temp
ptrs[row] += 1
return ans
由于矩阵是有序的，可以利用归并排序，但是由于每一轮需要遍历 N 次找出最小数，导致整体的时间复杂度比较高，可以用堆排序来优化
小顶堆 + 多路归并
class Solution:
class HeapSort:
def __init__(self, length):
self.length = length
self.heap = []
def add(self, num):
if len(self.heap) < self.length:
self.heap.append(num)
self._up()
elif num <= self.heap[0]:
self.heap[0] = num
self._down()
def get(self) -> int:
return self.heap[0]
def pop(self) -> int:
value = self.heap.pop(0)
if self.heap:
self.heap.insert(0, self.heap.pop())
self._down()
return value
def _up(self):
index = len(self.heap) - 1
while index > 0:
parent_index = (index + 1) // 2 - 1
if self.heap[parent_index] > self.heap[index]:
self.heap[parent_index], self.heap[index] = self.heap[index], self.heap[parent_index]
index = parent_index
else: break
def _down(self):
index = 0
child_index = index * 2 + 1
while child_index < len(self.heap):
if child_index + 1 < len(self.heap) and self.heap[child_index + 1] < self.heap[child_index]:
child_index += 1
if self.heap[child_index] > self.heap[index]: break
self.heap[child_index], self.heap[index] = self.heap[index], self.heap[child_index]
index = child_index
child_index = index * 2 + 1
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
heap = Solution.HeapSort(k)
for i in range(len(matrix)):
row = matrix[i]
heap.add((row[0], i, 0))
while k > 1:
k -= 1
_, i, j = heap.pop()
if j + 1 < len(matrix):
heap.add((matrix[i][j + 1], i, j + 1))
return heap.get()[0]
构建一个长度为 N 的小顶堆，就像优先级队列一样，每次 pop 出最小数及它所在的行和列，重复 k 次后得到解
二分查找
class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
def check(mid: int) -> bool:
count = 0
i, j = len(matrix) - 1, 0
while i >= 0 and j < len(matrix):
if matrix[i][j] <= mid:
count += i + 1
j += 1
elif matrix[i][j] > mid:
i -= 1
return count < k
left, right = matrix[0][0], matrix[-1][-1]
while left < right:
mid = (left + right) // 2
if check(mid):
left = mid + 1
else:
right = mid
return left
这是官方题解；典型的 leftmost 二分查找，将 left 一步步逼近最终解；由于是 leftmost，可以保证 left 是一定存在于矩阵中的
Review
BITCODE DEMYSTIFIED 一篇关于 Bitcode 技术细节的旧文，配合这篇旧文：Xcode 7 Bitcode的工作流程及安全性评估 基本上就能实现基于 Bitcode 的 hook。
Tip
前端开发中聊天场景的体验优化 IM 布局细节很多，我曾经也为 IM 的布局研究过好几种方案
- 将布局元素分为
Incoming、Outgoing两类，在一些 UI 设计中需要分别为消息方向实现不同的布局算法，增加了维护成本。JSQMessagesViewController和Telegram-iOS正是这么做的 - 利用
AutoLayout减少幻数的维护成本，但是纯AutoLayout会降低运行时性能，IM 列表对性能格外敏感 AutoLayout + Frame的方式，以模板里通过AutoLayout计算数值封装到模型里，然后将模型缓存起来，之后采用Frame的方式布局，尽量在维护性和运行性能之间达到一个平衡。实际对维护性并没有太多提高
而文中的方法提供了一种巧妙的思路，通过原地旋转的方式既能解决列表的方向问题，又能解决具体消息布局的问题，代码量少，维护性好，思路真好。
Share
最近在思考如何从程序员真正转型成合格的架构师，看到了架构视图这个知识点，对我有很大的启发，记录了5视图设计中的侧重点，希望之后能以思维导图的方式展示出来：
架构视图
逻辑架构
职责划分
- 逻辑层（Layer）
- 子系统、模块
- 关键类
职责间协作
- 接口
- 协作关系
开发架构
程序单元
- 源文件、配置文件
- 程序库、框架
- 目标单元
程序单元组织
- Project 划分
- Project 目录结构
- 编译依赖关系
数据架构
持久数据单元
- 文件
- 关系数据库
- 实时数据库
- Flash
数据存储格式
- 文件格式
- 数据库 Schema
运行架构
控制流
- 进程、线程
- 中断服务程序
控制流组织
- 系统启动与停机
- 控制流通信
- 加锁与同步
物理架构
物理节点
- PC、服务器
- 单片机、单板机、专用机
- 软件安装、部署、烧写
- 系统软件选型
物理节点拓扑
- 连接方式、拓扑结构
- 物理层（Tier）
- 冗余考虑