kth

CST PA4

4-3 Kth

算法构思

因为不能直接访问数组 a, b, c 中的元素, 我们定义数组 u, v, w, 将其初始化为 $\{1, 2, …, n\}$, 用于记录数组 a, b, c 中元素的 index.

将三元组视为三维空间中的点集, 我们需要返回点集之中坐标和第 k 小的三元组. 在 compare 接口中固定两维度 index 为 1, 我们可以比较单一维度的元素大小. 借此对三个数组分别进行快排, 排序结果反应在数组 u, v, w 中.

一般地, 若排序前数组 u 为 $\{1, 2, …, n\}$, 排序后为 $\{u[1], u[2], …, u[n]\}$, 即意味着数组 a 元素按大小升序排列为 $\{a[u[1]], a[u[2]], …, a[u[n]]\}$.

此时点集中坐标和最小的三元组即为 $a[u[1]], b[v[1]], c[w[1]]$. 我们维护一个最小堆 MinHeap, 将 $(1, 1, 1)$ 插入. 随后依次删除堆顶最小元组, 并插入坐标和恰好不小于删去堆顶坐标和的三元组.

第 k 次 Delete 得到的三元组 $(x, y, z)$ 对应的即是坐标和第 k 小的三元组 $a[u[x]], b[v[y]], c[w[z]]$.

对这个三维点集, 坐标和恰不小于 $(x, y, z)$ 的三元组必是 $(x, y, z + 1)$, $(x, y + 1, z)$, $(x + 1, y, z)$ 之一, 将其插入 MinHeap 即可. 考虑到同一个点可能会被压入多次, 调用 k 次 Delete() 后得到不是坐标和第 k 小的三元组, 特约定:

对于堆顶三元组 $(x, y, z)$, 我们插入 $(x, y, z + 1)$; 若 $z = 1$, 再插入 $(x, y + 1, z)$; 若 $y = z = 1$, 再插入 $(x + 1, y, z)$.

问题解决

• 在每次插入 $(x, y, z)$ 应该检查坐标是否合理, 否则会因非法插入, 使得 compare 函数报错.

复杂度估计

时间复杂度

对数组 a, b, c 进行快速排序, 时间复杂度为 $O(nlogn)$;

在维护 MinHeap 的过程中, 进行 k 次 Delete, 至多进行 3k 次 Insert, 时间复杂度为 $O(klogk)$.

综上, 算法总体时间复杂度为 $O(nlogn + klogk)$.

空间复杂度

数组 u, v, w 动态分配的空间为 $O(n)$, 堆 MinHeap 消耗的空间为 $O(k)$, 因此算法总体空间复杂度为 $O(n + k)$.

本题中直接在堆内开辟了相关大小的数组存储信息,

// Line 13
class MinHeap { // 实现一个三元之和最小堆.
    ...
private:
    int elem[4000100][3];
    int size = 0;
};

空间消耗最坏情况约为: $3\times 5\times 10^5 \times 4B + 1.2\times 10^7 \times 4B = 52MB < 256MB$, 符合题目要求范围.