查找两个有序序列合并后第k小元素的高效算法

作者 Shilei Tian 日期 2016-03-16
查找两个有序序列合并后第k小元素的高效算法

这周算法作业的最后一题是这样描述的:

You are given two sorted lists of size m and n in ascending order. Give an O(logm+logn) time algorithm for computing the kth smallest element in the union of the two lists.

说是有两个大小分别mn的有序序列,设计一个时间复杂度为O(logm+logn)的算法,来找出它们合并后序列中第k小的元素。我们很自然地想到了计数排序法,但是它的时间复杂度是O(m+n),不符合题目的要求。从O(log)上看,就可以想到要用二分查找法,但是二分法每次应该保留哪部分,扔掉哪部分呢?这就需要我们仔细地操作它。本篇文章的思想参考 LeetCode 上面的一篇文章,你可以在这里找到它。

既然要用二分法,那我们就从两个序列的中间的元素下手,设这两个序列分别为AB,中间的元素分别为A[i]B[j](下标从0开始)。如果A[i]介于B[j]B[j-1]之间,即B[j-1]<A[i]<B[j]的话,我们就刚好得到第i+j+1小的元素,我们可以结合下图考虑:


Figure 1

B[j-1]<A[i]<B[j]时,最终的序列中的三个元素必符合这样的相对位置,但是这三个元素不一定相邻。不过我们可以确定的是,新序列A[i]左面只包含它在原序列左边的元素和原序列BB[j-1]以及它左边的元素,那这样新序列A[i]左边共有i-1+1+j-1+1=i+j个元素,从而我们可得到A[i]一定是第i+j+1小的元素。那么同理可得,当A[i-1]<BA[j]<A[i]时,B[j]也一定是第i+j+1小的元素。有了这个作为铺垫,我们再想,如果能够让i+j=k-1,那么A[i]或者B[j]不就是题目要求的第k小的元素吗?

未完待续。