在 n 个数当中找第k小元素 (BFPRT算法,最坏情况为线性时间的选择问题)

题目描述

问题描述:

        在 n 个数当中找第k小元素。

输入:

        第一行输入n的值,第二行输入n个数,第三行输入k的值。

输出:

       n 个数中的第k小元素。

要求

       你的算法最坏情况下应该在线性时间内完成。

示例1 

输入:

5

8 1 3 6 9

3

输出: 6

 

示例 2

输入:

10

72 6 57 88 60 42 83 73 48 85

5

输出: 60

 

思路分析

       对于常规解法,我们随机在数组中选择一个数作为划分值(pivot),然后进行快排的partation过程(将小于pivot的数放到数组左边,大于pivot的数放到数组右边),划分完之后pivot的下标为i,然后判断k与等于i的相对关系,如果k正好在等于i,那么数组第k小的数就是pivot,如果k小于i,那么我们递归对左边再进行上述过程,如果k大于i,那我们递归对右边再进行上述过程。常规解法的应用及代码实现见这篇文章

        对于最好的情况:每次所选的pivot划分之后正好在数组的正中间,那么递归方程为T(n) = T(n/2) + n,解得T(n) = O(n),所以此时此算法是O(n)线性复杂度的。

        对于最坏情况:每次所选的pivot划分之后都好在数组最边上,那么时间复杂度为O(n2)。

       BFPRT算法就是在这个pivot上做文章,BFPRT算法能够保证每次所选的pivot划分之后在数组的中间位置,那么时间复杂度就是O(n)。

BFPRT算法流程

       这题规定了要在线性时间内完成第k小元素的选择,在算法导论这本书里面的第九章有讲解过这种问题,算法的基本思想是修改快速排序算法中的主元选取方法,降低算法在最坏情况下的时间复杂度。

  下述步骤来自《算法导论(第3版)》第9.3节。

       在快速排序中,我们始终选择第一个元素或者最后一个元素作为pivot,而在此算法中,每次选择五分中位数的中位数作为pivot,这样做的目的就是使得划分比较合理,从而避免了最坏情况的发生。通过执行下列步骤,算法Select可以确定一个有个不同元素的输入数组中第i小的元素:

(1) 将n个元素划为组,每组5个,至多只有一组由剩下的n mod 5个元素组成。

(2) 寻找这个组中每一个组的中位数,这个过程可以用插入排序,然后确定每组有序元素的中位数。  

(3) 对第2步中找出的个中位数,重复步骤1和步骤2,递归下去,直到剩下一个数字。

(4) 最终剩下的数字即为主元pivot,用快速排序的划分思想,把小于pivot的数全放左边,大于它的数全放右边。跟快速排序不同的是,这里只是划分,并没有排序。

(5) 判断pivot的位置与k的大小,有选择的对左边或右边递归。

  1 #include <iostream>
  2 #include <string.h>
  3 #include <stdio.h>
  4 #include <time.h>
  5 #include <algorithm>
  6  
  7 using namespace std;
  8  
  9 //插入排序
 10 void InsertSort(int a[], int l, int r)
 11 {
 12     for(int i = l + 1; i <= r; i++)
 13     {
 14         if(a[i - 1] > a[i])
 15         {
 16             int t = a[i];
 17             int j = i;
 18             while(j > l && a[j - 1] > t)
 19             {
 20                 a[j] = a[j - 1];
 21                 j--;
 22             }
 23             a[j] = t;
 24         }
 25 }
 26 }
 27  
 28 //寻找中位数的中位数
 29 int FindMid(int a[], int l, int r)
 30 {
 31     if(l == r) return l;
 32     int i = 0;
 33     int n = 0;
 34     for(i = l; i < r - 5; i += 5)
 35     {
 36         InsertSort(a, i, i + 4);
 37         n = i - l;
 38         //插入排序之后,a[i+2]就是a[i,...,i+5]的中位数
 39         //把中位数都放到前面 
 40         swap(a[l + n / 5], a[i + 2]);
 41     }
 42  
 43     //处理剩余元素
 44     int num = r - i + 1;
 45     if(num > 0)
 46     {
 47         InsertSort(a, i, i + num - 1);
 48         n = i - l;
 49         swap(a[l + n / 5], a[i + num / 2]);
 50     }
 51     n /= 5;
 52     if(n == l) 
 53         return l;
 54     
 55     //前n个数就是上述找出来的每一组的中位数 
 56     return FindMid(a, l, l + n);
 57 }
 58  
 59 //进行划分过程,就是一趟快速排序的过程,返回划分后的基准数的下标i 
 60 int Partition(int a[], int l, int r, int p)
 61 {
 62     swap(a[p], a[l]);
 63     int i = l;
 64     int j = r;
 65     int pivot = a[l];
 66     while(i < j)
 67     {
 68         while(a[j] >= pivot && i < j)
 69             j--;
 70         while(a[i] <= pivot && i < j)
 71             i++;
 72         swap(a[j], a[i]);
 73     }
 74     swap(a[l], a[i]);
 75     
 76     return i;
 77 }
 78  
 79 int Select(int a[], int l, int r, int k)
 80 {
 81     int p = FindMid(a, l, r);       //寻找中位数的中位数
 82     int i = Partition(a, l, r, p);  //划分之后的下标 
 83  
 84     int m = i - l + 1;
 85     if(m == k) 
 86         return a[i];
 87     if(m > k)  
 88         return Select(a, l, i - 1, k);
 89         
 90     return Select(a, i + 1, r, k - m);
 91 }
 92  
 93 int main()
 94 {
 95     int n, k;
 96     scanf("%d", &n);
 97     int *a = new int[n];
 98     for(int i = 0; i < n; i++)
 99         scanf("%d", &a[i]);
100     scanf("%d", &k);
101     printf("%d", Select(a, 0, n - 1, k));
102     
103     delete[] a;
104     return 0;
105 }

 

复杂度分析

在 n 个数当中找第k小元素 (BFPRT算法,最坏情况为线性时间的选择问题)

 

在 n 个数当中找第k小元素 (BFPRT算法,最坏情况为线性时间的选择问题)

思考与引申

        快速排序的 Partition 划分思想可以用于计算某个位置的数值等问题,可以实现 O(n)复杂度的选择问题,之所以这种选择算法具有线性时间,是因为没有进行排序,并且每次都有选择的只对左右其中的一边进行递归处理,而排序需要进行比较,并且快速排序左右两边都需要进行递归处理,即使是在平均情况下,排序也需要 O(nlogn)的时间复杂度,而这个线性时间的选择算法没有使用排序就解决了选择问题。

优缺点

        但缺点也很明显,最主要的就是内存问题,在海量数据的情况下,很有可能没办法一次性将数据全部加载入内存,这个时候这个方法就无法完成使命了。此时可以利用堆来解决,维护一个大小为 K 的小顶堆,依次将数据放入堆中,当堆的大小满了的时候,只需要将堆顶元素与下一个数比较:如果大于堆顶元素,则将当前的堆顶元素抛弃,并将该元素插入堆中。遍历完全部数据,Top K 的元素也自然都在堆里面了。但是使用堆解决这个问题,时间花费为 O(nlogn)。

 

参考

《算法导论 (第3版)》 第9.3节

bfprt算法解析

知乎 - BFPRT算法原理

 

相关习题

剑指 Offer 40. 最小的k个数

上一篇:快速排序为什么这么快?


下一篇:剑指 Offer | 29. 顺时针打印矩阵