进阶班01.md

高级班第1节

一、BFPRT

1. 问题引入

在一个无序数组中，求第k大/小的数

2. 解决办法

• 傻瓜式：排序，索引

• 高级方法：bfprt算法，$O(n)$

3. 推导过程

快排思想，如果只取满足要求的一侧进行下一次递归，则在概率上可以将时间复杂度降为$O(n)$，而因为快排思想中基准位置是随机选择的，所以只能在概率上证明是$O(n)$，bfprt算法没有优化复杂度，只是将概率证明变为了非概率证明，可以理解为装逼用

4. 力扣题目

题目链接：215. 数组中的第K个最大元素

• 普通快排：

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int left = 0;
        int right = nums.size()-1;
        int index = partition(nums, left, right);
        while ((index+1) != k) {
            if ((index+1) < k) {
                left = index+1;
                index = partition(nums, left, right);
            } else {
                right = index-1;
                index = partition(nums, left, right);
            }
        }
        return nums[index];
    }
    int partition(vector<int>& nums, int left, int right) {
        int std = left + (rand() % (right-left+1));
        swap(nums[left], nums[std]);
        int index = left+1;
        for (int i = index; i <= right; ++i) {
            if (nums[i] >= nums[left]) {
                swap(nums[i], nums[index]);
                index++;
            }
        }
        swap(nums[left], nums[index-1]);
        return index-1;
    }
};

• bfprt：其实就是将随机选择基准索引变为了选择中位数的数组的中位数这个操作，递归调用bfprt这个操作有点意思，不是之前见过的递归调用自身，或者递归调用某个子函数，而是子函数递归调用父函数

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int left = 0;
        int right = nums.size()-1;
        // 返回排序情况下，k-1位置上的数
        return bfprt(nums, left, right, k-1);
    }
    int bfprt(vector<int>& nums, int left, int right, int k) {
        if (left == right) {
            return nums[left];
        }
        // 精挑细选一个数（上中位数）
        int pivot = midOfMids(nums, left, right);
        int index = partition(nums, left, right, pivot);
        if (index == k) {
            return nums[index];
        } else if (index < k) {
            left = index+1;
            return bfprt(nums, left, right, k);
        } else {
            right = index-1;
            return bfprt(nums, left, right, k);
        }
    }
    int midOfMids(vector<int>& nums, int left, int right) {
        int size = right - left + 1;
        int offset = size % 5 == 0 ? 0 : 1;
        int len =  size / 5 + offset;
        vector<int> midarr(len, 0);
        for (int i = 0; i < len; ++i) {
            int start = left + i*5;
            int end = min(right, start+4);
            // 在c++的sort函数中，迭代器是指针需要移动的步数，所以要移动5步
            // 调用sort不要忘了加谓词，从大到小
            sort(nums.begin()+start, nums.begin()+end+1, greater());
            int retIdx = (start+end) / 2;
            midarr[i] = nums[retIdx];
        }
        return bfprt(midarr, 0, len-1, (len-1)/2);
    }
    int findIdx(vector<int>& nums, int pivot) {
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] == pivot) {
                return i;
            }
        }
        return -1;
    }
    int partition(vector<int>& nums, int left, int right, int pivot) {
        int std = findIdx(nums, pivot);
        swap(nums[left], nums[std]);
        int index = left+1;
        for (int i = index; i <= right; ++i) {
            if (nums[i] >= nums[left]) {
                swap(nums[i], nums[index]);
                index++;
            }
        }
        swap(nums[left], nums[index-1]);
        return index-1;
    }
};

在力扣的系统中，bfprt算法实际的效率并没有快速选择高，尴尬，一方面是我在partition过程中不会直接根据值进行操作，比较笨的将值转化为索引，这个之后想办法再优化一下