第三批

1822. 电话拦截（模拟、排序）

难度：中等；主观评价：简单。

sort.Slice() 应用题，重点在于通配符的判断和如何设计数据结构保证最后能按呼叫顺序返回通话记录。

对于没有通配符的号码，可以使用 map 保存，使用时判断 map 中是否包含对应的 key；对于有通配符的号码可以去掉结尾的 * 号后使用数组保存，使用时遍历这个数组并用 strings.HasPrefix() 判断当前的电话号码是否满足某个带有通配符的匹配规则。

使用 map 保存通话记录可以很方便地编辑某个号码的通话记录信息。由于 Go 的 map 是无序的，所以在设计保存结构时，需要加上序号，并且在每次向这个 map 添加新元素（即新增通话记录）时都更新这个序号，最后使用 sort.Slice() 按照序号排序并生成所需格式即可。

时间复杂度：O(n * m)，其中 m 为输入的白名单中带有通配符的电话号码的个数。

空间复杂度：O(n)，record 哈希表占用的空间与输入中不同电话号码的个数成正比。

1825. 按身高和体重排队（排序）

难度：简单；主观评价：简单。

sort.Slice() 应用题。

为了便于理解和编码，这里将每一位运动员的数据都保存在一个结构体中，然后对这个结构体数组进行排序，最后把所有运动员的编号按顺序收集到一个切片中返回。

当然这道题如果想优化到极致的话可以将空间复杂度优化到 O(1)，具体方法是直接生成答案数组并参考要求对答案数组排序。

时间复杂度：O(nlogn)，为排序算法的时间复杂度。

空间复杂度：O(n)，主要来自 students 数组。

1826. 整数对最小和（TopK）

难度：简单；主观评价：中等。

先吐槽一下这令人迷惑的难度评级，TopK 竟然评了个简单？且不说这题在算法难度上完爆被评为中等的 1822，LeetCode 上最简单的 TopK（LeetCode 215.Kth Largest Element in an Array）都是中等。。。这要是哪位不会 TopK 的倒霉蛋在入门级科目一抽到这种题，估计他的内心是崩溃的。

言归正传，既然是 TopK 问题且寻找的是最小的 k 个和，那么我们可以建立一个大小为 k 的大顶堆，并且遍历两个数组枚举每一对整数和。当堆没满时，可以将和直接加入堆；当堆满后，如果和小于堆顶，就弹出堆顶并且把和加入堆；如果和大于堆顶，则直接跳过，并且由于两个数组都是已经排好序的，所以此时可以直接跳过剩余的数。最后把堆中元素加起来即得到答案。

这题对于 Go 语言的主要难点是如何实现一个堆（实现 heap.Interface），以及自行实现 peek() 方法：从堆中弹出一个元素再将它插入回去。

时间复杂度：O((n*m)logk)，其中 n 为 array1 的长度，m 为 array2 的长度，logk 为将堆调整为大顶堆的时间复杂度。

空间复杂度：O(k)，堆占用的空间与 k 成正比。