极客时间:数据结构与算法之美笔记

排序(下):如何用快排思想在 ○(n) 内查找第 k 大元素

2019-01-10  本文已影响0人  红酥手黄藤酒丶

排序(下):如何用快排思想在 ○(n) 内查找第 k 大元素

快排核心思想就是 分治分区,我们可以利用分区的思想,来解答此问题。比如,4,2,5,12,3 这样一组数据,第 3(k=3)大元素就是 4。

这个思想与二分查找的思想很像。我们可以选择数组区间 A[0...n-1] 的最后一个元素 A[n-1] 作为 pivot 分区点,对数组 A[0...n-1] 原地分区,这样数组就分成了三部分,A[0...p-1]、A[p]、A[p+1...n-1]。

如果 p+1=K,那 A[p] 就是要求解的元素;如果 K>p+1,说明第 K 大元素出现在 A[p+1...n-1] 区间,我们再按照上面的思路递归地在 A[p+1...n-1] 这个区间内查找。同理,如果 K<p+1,那我们就在 A[0...p-1] 区间查找。

那么关键问题就是,为什么上述解决思路的时间复杂度是 ○(n)?

第一次分区查找,我们需要对大小为 n 的数组执行分区操作,需要遍历 n 个元素。第二次分区查找,我们只需要对大小为 n/2 的数组执行分区操作,需要遍历 n/2 个元素。依次类推,分区遍历元素的个数分别为:n/2 n/4 n/8 n/16......直到区间缩小为 1。

如果我们把每次分区遍历的元素个数加起来,就是:n + n/2 + n/4 + n/8 +...+ 1。可以发现,这是一个等比数列求和的过程,等比数列求和公式:2n-1。所以上述相加的和就是:2n-1。 所以时间复杂度就为 ○(n)。

image

思考问题:

image

评论区的大神的思路:


image image image
上一篇 下一篇

猜你喜欢

热点阅读