bfprt

bfprt

//找第k小的数 or 找第n-k大的数

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

class Solution

{

public:

    int getMinKByBFPRT(vector<int>& arr,int k)

    {

        if(k<||k>arr.size())

            return ;

        vector<int> tmp(arr.begin(),arr.end());

        return bfprt(tmp,,tmp.size()-,k);

    }

private:

    int bfprt(vector<int>& arr,int left,int right,int k)

    {

        if(left==right)

            return arr[left];

        //1.得到中位数

        int pivot=getMedian(arr,left,right);

        //2.根据中位数划分左右区间

        vector<int> pivotRange(_partition(arr,left,right,pivot));

        //3.找到中位数排序后的位置，判断k是不是中位数所在的下标范围内，如果在就找到了

        if(k>=pivotRange[]&&k<=pivotRange[])

            return arr[k];

        else if(k<pivotRange[])

            return bfprt(arr,left,pivotRange[]-,k);

        else /*if(k>pivotRange[1])*/

            return bfprt(arr,pivotRange[]+,right,k);

        //return 0;

    }

    int getMedian(vector<int>& arr,int left,int right)

    {

        int nums=right-left+;

        int offset=nums%==?:;//每五个为一组，求每组的中位数，放在中位数数组中

        vector<int> midArr(nums/+offset);//中位数数组

        for(int i=;i<midArr.size();++i)

        {

            int l=left+i*;

            int r=l+;

            midArr[i]=getMedianCore(arr,l,min(r,right));

        }

        //找中位数组的中位数

        return bfprt(midArr,,midArr.size()-,midArr.size()/);

    }

    int getMedianCore(vector<int>& arr, int left, int right)

    {

        //中位数组排序，返回中间数

        sort(arr.begin()+left,arr.begin()+right+);

        return arr[(left+right)/+(left+right)%];//奇数和偶数情况

    }

    vector<int> _partition(vector<int>& arr,int left,int right,int pivot)

    {

        int small=left-;//small总是指向当前最小的位置，初始化为数组的首元素的前一位置

        int big=right+;//big总是指向当前最大的位置，初始化为数组的尾元素的后一位置

        int cur=left;

        while(cur<big)

        {

            if(arr[cur]<pivot)

                swap(arr[++small],arr[cur++]);

            else if(arr[cur]>pivot)

                swap(arr[cur],arr[--big]);

            else

                ++cur;

        }

        vector<int> tmp{small+,big-};

        return tmp;

    }

};

int main()

{

    Solution s;

    vector<int> arr{};

    cout<<s.getMinKByBFPRT(arr,)<<endl;

    return ;

}