2.4.7

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

k = 2 时,
只可能出现在位置 2、3 上(根节点的子结点,深度为 2,根节点深度为 1)
k = 3 时,
可以直接是根节点的子结点(第 2 或第 3 位,深度为 2),
也可以是第二大元素的子结点(第 4~7 位,也就是深度为 3 的所有位置)
k = 4 时,
可以直接是根节点的子结点(深度为 2 的点)
也可以是第二大元素的子结点(深度为 3 的点)
也可以是第三大元素的子结点(深度为 4 的点)
故范围为第 2~15 位。

不难看出第 k 大元素只可能出现在深度<k 的位置($ k \ge 2 $)
即位置小于 $ 2 ^ k - 1, (k \ge 2) $

上一题 下一题