《算法设计手册》杂题三道

《算法设计手册》杂题3道

　　最近找工作的事告一段落，发一些之前整理但未发表的文章。鉴于各个公司一般要求将所做笔试题和面试题保密，并要求在试卷上签署了相关协议，因此本人不会在后续博文中提及并分析，见谅。

归纳并证明下面函数的输出：

　　实例2：第k小的元素大于等于x。原图交换顺序。

　　实例3：第k小的元素小于x。

　　从上面三个例子可以看出：

　　每找到一个小于x的元素都会消耗一个count，如果消耗完了k个，表示至少前k个都小于x。那么第k个必然小于x，后面不必再进行查找，返回值为0。

　　反之，如果遍历所有小于k的元素时未消耗完k个count，表示小于x的元素不足k个，那么第k个必然大于等于x，返回值为正值。

　　原代码中令人迷惑的地方在于count的使用，理清上面的两个关系就好理解了。虽然看上去这个函数对于一个结点的两个后继的处理地位不同，但实际上没有影响。

　　至于时间复杂度，由于我们只遍历了所有小于x的结点以及它们的后继，而且遍历时不超过k个（用完k个就return 0），因此大约是3k个结点，时间复杂度只有O(k)，符合要求。

　　这道题曾在Amazon的面试中出现。

　　stackoverflow上有一个变形：判断n元最大堆中第k大的元素是否大于给定的数x，处理方法类似。