【搞定算法】BFPRT 算法、快排解决第 k 大数问题

梦里梦外; 2021-12-14 02:32 243阅读 0赞

博主秋招提前批已拿百度、字节跳动、拼多多、顺丰等公司的offer，可加微信：**pcwl\_Java**  一起交流秋招面试经验。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70][]

### **目  录：** ###

方法1：暴力解法

方法2：快排实现【笔试版+面试版】

方法3：BFPRT 算法实现【面试优化版】

--------------------

> **问题：求一个数组中的第 k 小 / 大的数。**
> 
> **说明：这道题求解不难，主要的目的是为了引出 快排算法的应用（partiotion）和 BFPRT 算法**

## 方法1：暴力解法 ##

其实我们很容易想到先将这个数组排好序，再直接取出数组中下标为 k - 1 的数即可。

public class FindKthNumByQuickSort {
    
        // 暴力解法
        public static int getKthNum(int[] arr, int k){
            if(arr == null || arr.length < 1 || k < 0){
                return Integer.MIN_VALUE;
            }
    
            Arrays.sort(arr);
            return arr[k - 1];
        }
    }

--------------------

## 方法2：快排实现【笔试版+面试版】 ##

快速排序将比关键字大的元素从前面移动到后面，比关键字小的元素从后面直接移动到前面，从而减少了总的比较次数和移动次数，同时采用”分而治之“的思想，把大的拆分为小的，小的再拆分为更小的，其原理如下：通过一趟排序将待排序的数组分成两个部分，其中一部分记录的是比关键字更小的，另一部分是比关键字更大的，然后再分别对着两部分继续进行排序，直到整个序列有序；

步骤：代码也很容易理解，其实就是一个“填坑”的过程，

1、第一个“坑”挖在每次排序的第一个位置 arr\[low\]，从序列后面往前找第一个比 pivot 小的数来把这个“坑”填上，这时候的“坑”就变成了当前的 arr\[high\]；

2、然后再从序列前面往后用第一个比 pivot 大的数把刚才的“坑”填上；

3、如此往复，始终有一个“坑”需要我们填上，直到最后一个“坑”出现，这个“坑”使用一开始的 pivot 填上就可以了，而这个“坑”的位置也就是 pivot 该填上的正确位置，我们再把这个位置返回，就可以把当前序列分成两个部分。再依次这样操作最终就达到排序的目的了【为什么 low 和 high 相遇处就是 pivot 的位置？因为 high 右边一定是 >= pivot的，low 左边一定是 <=pivot 的，所以它们相遇处就是 pivot】

说明：快排的 partition 函数有很多的应用，主要它可以将一个数组基于 key 划分成大于它的和小于它的两部分，利用这个 key 的下标可以做很多事情。

public class FindKthNumByQuickSort {
    
        public static void quickSort(int[] arr, int k){
            if(arr == null || arr.length < 1){
                return;
            }
            int low = 0;
            int high = arr.length - 1;
            quick(arr, low, high, k);
            System.out.println(arr[k]);
        }
    
        public static int[] quick(int[] arr, int low, int high, int k){
    
            // 获取分割点
            int index = partition(arr, low, high);
            // 下标是从0开始的，所以k要减1
            if(k - 1 == index){
                System.out.println("第 " + k + " 大元素为：" + arr[index]);
            }
            if(k - 1 < index){
                // 左半部分查找
                quick(arr, low, index - 1, k);
            }
    
            if(k - 1 > index){
                quick(arr, index + 1, high, k);
            }
            return arr;
        }
    
        public static int partition(int[] arr, int low, int high){
            // 固定的切分方式
            int key = arr[low];
            while(low < high){
                // 从后半部分往前半部分扫描
                while(high > low && arr[high] >= key){
                    high--;
                }
                // 交换位置，把后半部分比基准点位置元素值小的元素交换到前半部分的low位置处
                arr[low] = arr[high];
    
                // 从前半部分往后半部分扫描
                while(high > low && arr[low] < key){
                    low++;
                }
                arr[high] = arr[low];
            }
            arr[high] = key;
            return high;
        }
    }

--------------------

## 方法3：BFPRT 算法实现【面试优化版】 ##

**与快排实现的区别在于它不是随机选择用于划分的那个数，而是选择中位数组的中位数，这样选出的数能保证左右两边都至少有 3N/10 的数据，而不像随机选择那样左右两边数据量不确定。**

*  ### **算法流程：** ###

**1、得到中位数组中的中位数**

1.1、相邻 5 个数为一组（0-4，5-9.....），最后一个组剩几个就有几个\[因为是逻辑上的划分，所以不花时间\]；

1.2、每一个小组内排序【5 个数排序是O（1），共有约 N/5 个小组，所以时间复杂度是 O(N/5)】；

1.3、把每个小组中的中位数拿出来组成一个新数组：中位数数组 【因为长度为 N/5, 所以是 O(N)】；

1.4、递归调用 bfprt ，求出中位数数组的中位数【bfprt 解决的是第 k 大的问题，即排好序后位于 k-1 的数】\[时间复杂度 T(N/5)\]。

**2、快排划分区间**

可以采用荷兰国旗问题的解决方案将原数组划分成三堆，看 = 部分位置有没有命中 k，如果没有，且 位置 < k ，那么排右边，否则排左边，知道命中就返回 【因为选出的数能保证左右两边都至少有 3N/10 的数据，即下一次最多只有 7N/10 的数据，因为是递归，所以时间复杂度是 T(7N/10)】。

*  ### 时间复杂度 ###
 *  **BFPRT 时间复杂度为 ：T(N) = T(N/5) + T(7N/10) + O(N) +O（N/5) => O（N）**

为什么选出的数能保证左右两边都至少有 3N/10 的数据？

我们先把数每五个分为一组。同一列为一组。排序之后，第三行就是各组的中位数。我们把第三行的数构成一个数列，递归找，找到中位数。这个黑色框为什么找的很好。因为他一定比A3、B3大，而A3、B3、C3又在自己的组内比两个数要大。我们看最差情况：就算其它的数都比 C3 大，也至少有 3/10 的数据比它小。

![20190707155316121.png][]

*  ### 代码实现 ###

public class BFRPT {
    
        public static int getMinKth(int[] arr, int k){
            if(arr == null || arr.length == 0 || k < 0 || k >= arr.length){
                return Integer.MIN_VALUE;
            }
    
            //返回从小到大，位于 k-1 位置的数字，就是第 k 大的数
            int res = bfrpt(arr, 0, arr.length - 1, k - 1);
            System.out.println(res);
            return res;
        }
    
        // 在 left,right 范围上，找到从小到大排序为 p 的数，即为第 p+1 小的数
        public static int bfrpt(int[] arr, int left, int right, int p){
            if(left == right){
                return arr[left];
            }
    
            // bfrpt算法：选择中位数数组中的中位数来作为基准划分原数组，可以每次确定甩掉 3N/10 的数据量
            int num = medianOfMedians(arr, left, right);
            int[] index = partition(arr, left, right, num);
            if(p >= index[0] && p <= index[1]){
                return arr[p];
            }else if(p < index[0]){
                return bfrpt(arr, left, index[0] - 1, p);
            }else{
                return bfrpt(arr, index[1] + 1, right, p);
            }
        }
    
        // 根据数num作为基准对数组arr上left到right的范围进行划分（快排/荷兰国旗）
        public static int[] partition(int[] arr, int left, int right, int num){
            int less = left - 1;
            int more = right + 1;
            int cur = left;
            while(cur < more){
                if(arr[cur] < num){
                    swap(arr, ++less, cur++);
                }else if(arr[cur] > num){
                    swap(arr, --more, cur);
                }else{
                    cur++;
                }
            }
            return new int[]{less + 1, more - 1};
        }
    
        // 求中位数数组中的中位数
        public static int medianOfMedians(int[] arr, int left, int right){
            int num = right - left + 1;
            int offset = num % 5 == 0 ? 0 : 1;
            int[] mArr = new int[num / 5 + offset];  // 中位数数组
            int index = 0;
            for(int i = left; i < right; i = i + 5){
                // 从1开始，而不是从0开始
                mArr[index++] = getMedian(arr, i, Math.min(right, i + 4));
            }
            return bfrpt(mArr, 0, mArr.length - 1, mArr.length / 2);
        }
    
        public static int getMedian(int[] arr, int left, int right){
            insertSort(arr, left, right);
            return arr[(left + right) / 2];
        }
    
        // 因为只对5个数排序，所以选择插入排序
        public static void insertSort(int[] arr, int left, int right){
            for(int i = left + 1; i <= right; i++){
                // 在前面的有序数组中找到自己的位置
                for(int j = i; j > left; j--){
                    if(arr[j - 1] > arr[j]){
                        swap(arr, j - 1, j);
                    }else{
                        break;
                    }
                }
            }
        }
    
        public static void swap(int[] arr, int i, int j){
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    
        public static void main(String[] args) {
            int[] arr = {6, 9, 1, 3, 1, 2, 2, 5, 6, 1, 3, 5, 9, 7, 2, 5, 6, 1, 9};
            getMinKth(arr, 5);
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190902171750658.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2,size_16,color_FFFFFF,t_70
[20190707155316121.png]: /images/20211213/4c4fce79ee934487841cd0cfc7880437.png