BFPRT算法-Golang

这个BFPRT算法找逻辑Bug找了两天

注意点:

  1. 在找中位数的时候对传入的数组进行排序,这里使用直接插入排序,因为元素个数最多为5,插排常数项极低
    1. 注意:这里不是nums[j] > nums[i]而是for j = i - 1; j >= start && nums[j] > temp; j-- {,因为后面会对nums[i]造成修改
  2. 找中位数数组的中位数medianOfMedians返回的是最终的中位数的值,我们使用这个值进行Partition,自己这里还一直将其当做返回的索引用,导致越界
  3. BFPRT函数调用自己的时候,参数一定要对应,自己在写的时候直接将k传入了start

具体流程:

其实BFPRT算法与我们之前的快排唯一的区别就在于选择划分元素,之后的partition过程与我们的荷兰国旗划分是一样的。

note info 应用场景:无序数组中找到第K小或第K大的数,也可以找到前K大或前K小的数,因为快速排序的partition长期期望时间复杂度为O(N)而BFPRT算法的时间复杂度稳定在O(N)

具体流程

wTcpJO

  1. 将数组按照5个元素分成一组,最后一组不足5个元素的自成一组,时间复杂度:O(1)
  2. 组内排序,并将所有数组的中位数组成一个新数组,时间复杂度:O(N)
  3. 获得新数组的中位数,使用这个中位数进行partition(partition与我们荷兰国旗问题保持一致),时间复杂度:O(N)
  4. 之后判断我们要的第k小或者第k大是否在对应区间内,如果在的话就直接返回,否则选择一侧继续递归,*时间复杂度:O(7/10 * n)*

如何求前k大或者前k小呢?

这里我们的BFPRT算法返回的是第k小的数,但是如果我们想要返回前k小或者前k大的数,我们需要再对数据进行一次遍历,找到比该数小的,如果不够,再加入该数,直到找到k个为止进行返回,同理前k大的数可以转换为长度-k小的,求出之后按照上述思路求得我们最终的前k大的数即可