Interview Questions 2: Find Kth element in union of sorted arrays

题目:  给M个数组, 每个数组都是升序,让返回所有数里面第K小的元素.

解法1: 既然有M个这样的排好序的数组, 做一个大小M的Min-Heap, 把每一行数组的第一个元素放进去, 每次都pop出最小的元素, 直到pop出第K个元素就是我们的答案. 时间复杂度O(M + KlogM).

解法2: 任意去除某一个数组里面的某一个数t, 在每个数组里面都进行二分法判断出t所在的位置顺序, 复杂度大概是O(MlogNi), Ni 是每个数组的元素个数, 这样完成以后就可以轻松判断有多少个数恰好比t小, 设有C个数字恰好比t小, 如果C == K-1 那么t就是我们的答案. 如果C > K – 1, 那么说明所有比t大的都不可能是第K的元素, 去掉每个数组里面比t大的部分, 在剩下的部分里面寻找第K小的数字,  如果C < K-1 那么, 说明比t小的所有数都不可能是我们要的答案,于是去掉每个数组里面比t小的部分, 然后再剩下的数里面寻找第K – C小的数就是我们的答案. 假设这M个数组总共有S个元素, 如果数分布均匀的话, 基本上没进行一次O(MlogNi)这样的帅选可以去除S/2个部分, 还是类似二分法, 所以会有大概logS次O(MlogNi)的筛选. 总体算法的复杂度大概是O(MlogNi * log S).

注意: 二分法写起来还是很麻烦的, 第一个方法比较适合当场写.

 

(全文完,原创文章,转载时请注明作者和出处)


(转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com,请勿用于任何商业用途)

Written on September 11, 2013