BFPRT

https://blog.csdn.net/qq_40938077/article/details/81213820#commentBox

"""
BFPRT算法，简称 TOP K 问题，用来求数组中第k小元素的算法
    - BFPRT是快速选择算法的改进版，改进了对基准的选取
    - 可以在O（n）时间内求出答案

    - Niubility !!
"""

import random


class Solution:
    # 快速选择排序算法，平均情况O(n)，最坏情况O(n^2)，还不错，不过还有更好的算法：BFPRT
    def findKthLargest(self, nums, k):
        def getmedian(lis):
            """返回lis中位数"""
            begin = 0
            end = len(lis)-1

            sum = begin+end
            mid = sum//2 + sum%2
            # print(lis)
            # print('返回：', sorted(lis)[mid])
            return sorted(lis)[mid]
        # int getmedian(int root[],int beginI,int endI)//这个函数求的是在root数组中beginI位置到endI位置上的中位数（其实就是求由每5个数所分成的小组的小组内的中位数）
        # {
        #     sort(root+beginI,root+endI+1);
        #     int sum=beginI+endI;
        #     int mid=(sum/2)+(sum%2);//这个地方加上sum%2是为了确保偶数个数时我们求的是中间两个数的后一个
        #     return root[mid];
        # }

        def BFPRT(nums, left, right):
            num = right-left+1
            offset = 0 if num % 5 == 0 else 1
            groups = num//5 + offset
            median = []  # 中位数数组
            for i in range(groups):
                begin = left+i*5
                end = begin + 4
                # print(nums[begin:min(end, right)+1])
                Median = getmedian(nums[begin:min(end, right)+1])
                median.append(Median)
            print("中位数数组：", median)
            return select(median, 0, groups-1, groups//2)
        # int medianOfMedians(int root[],int star,int finish)//这个函数是将root数组star位置到finish位置分成每5个数一个小组，并求出每个小组内的中位数
        # {
        #     int num=finish-star+1;//求出长度  【6】
        #     int offset=num%5==0?0:1;//最后如果剩余的数不足5个，我们也将其分成一个小组，和前面同等对待
        #     int range=num/5+offset; 【2组】
        #     int median[range];//这个数组存的是每个小组内的中位数
        #     for(int i=0;i<range;i++)//依次往median数组中填数
        #     {
        #         int beginI=star+i*5;//第i组数对应root数组上的位置
        #         int endI=beginI+4;
        #         median[i]=getmedian(root,beginI,min(endI,finish)); 【0-4】、【5-5】
        #     } median = [3, 4]
        #     return bfprt(median,0,range-1,range/2);//求出生成好的median数组的中位数，作为partation函数的划分值
        # }

        def partition(nums, left, right, base):
            """
            在 nums[left, right] 将基准base归位
            """
            temp = nums[base]
            nums[base], nums[right] = nums[right], nums[base]  # 基准和末尾元素互换

            max_index = left
            for i in range(left, right):  # 把所有小于基准的移到左边
                if nums[i] <= temp:  # 要等于啊！这里好坑的说..
                    nums[max_index], nums[i] = nums[i], nums[max_index]
                    max_index += 1

            nums[right], nums[max_index] = nums[max_index], nums[right]  # 基准归位
            return max_index

        def select(nums, left, right, k_smallest):
            """
            在 nums[left, right] 找第k小的元素
            """
            if left == right:  # 递归终止条件
                return nums[left]
            # pivot_index = random.randint(left, right)
            base = BFPRT(nums, left, right)
            print('找到的基准为', base, nums)
            base_index = nums.index(base)
            print(base_index)
            base_index = partition(nums, left, right, base_index)  # 选第一个(left)为基准，并归位。
            print("base_index:", nums)
            if base_index == k_smallest:  # 判断目前已归位的基准，是不是第k_smallest位
                return nums[k_smallest]
            elif k_smallest < base_index:  # 递归左半部分
                return select(nums, left, base_index - 1, k_smallest)
            else:  # 递归右半部分
                return select(nums, base_index + 1, right, k_smallest)
        ans = select(nums, 0, len(nums) - 1, len(nums) - k)  # 第k大，是第n-k小
        print(nums)
        return ans


s = Solution()
print(s.findKthLargest([3, 3, 3, 3, 4, 3, 3, 3, 3], 1))

BFPRT

原文：https://www.cnblogs.com/ldy-miss/p/12031077.html