有趣的CS - 别急求值
别急! 别急! 我们先别急着切入正文,而是先看看一道算法题: 圆角骑士魔理沙:数组多次取第X大元素 大家在评论区可以看到,这道题有一定的难度:不少人给出了错误,或者超时的答案。 尽管最高赞给出的答案的确是正确的,其实有一个简单很多的做法: 对N生成二叉搜索树,然后用M索引之。 等下,这不是O(n log n)的吗? 所以才说别急!我们想一想,当M < N的时候,这个二叉树,并不是所有节点,都会被索引。 那,我们为什么要去把不会被用的二叉树部分构建出来捏? 但是,我们怎么知道‘树的那一部分会被用上’? 答案是,我们可以同时交叉构建树跟索引树的过程 - 默认情况下,树是没构建的。当我们索引没被构建过的树,我们会构建这里的最小一部分,然后保存下结果,再进行构建。 class LazyBST: def __init__(self, arr): self.constructed = False self.arr = arr self.size = len(arr) def idx(self, index): if not self.constructed: self.constructed = True self.head = self.arr[0] self.left = LazyBST([x for x in self.arr[1:] if x <= self.head]) self.right = LazyBST([x for x in self.arr[1:] if x > self.head]) if index < self....