找无序数组中最小的k个数

题目描述

  给定一无序的整型数组arr,找到其中最小的k个数。

排序方法

算法思想

  排序的方法是最容易想到的方法,但是此时算法的复杂度和使用的排序算法时间复杂度相同,如果使用快速排序便是O(NlogN)。使用排序算法将数组按照从大到小变为有序之后直接取排在前面的k个数字即可。

代码实现

//快速排序
void quickSort(vector<int> &v,int left,int right){
    if(left>=right) return;
    int i=left,j=right;
    int pivot = v[left];
    while(i<j){                             //划分过程
        while(i<j&&v[j]>=pivot) j--;
        v[i]=v[j];
        while(i<j&&v[i]<=pivot) i++;
        v[j]=v[i];
    }
    v[i]=pivot;
    quickSort(v,left,i-1);                      //递归处理左右两个区间
    quickSort(v,i+1,right);
}
//获取数组中最小的k个元素
vector<int> getMinKNumsByQuickSort(vector<int> arr, int k){
    quickSort(arr,0,arr.size()-1);
    return vector<int>(arr.begin(),arr.begin()+k);
}

维护大根堆的方法

算法思想

  维护一个有k个元素组成的大根堆。每次将数组中的一个元素和堆顶元素比较,如果比堆顶元素小,那么则和堆顶元素交换并调整堆。直到遍历完所有元素,堆中便是数组中最小的k个元素。这里因为要维护和调整一个大小为k的堆,并且需要遍历一遍数组中的元素,所以算法的时间复杂度为O(Nlogk)。

代码实现

//调整一个堆,使之满足大根堆
void heapAdjust(vector<int> &arr,int begin, int end){
    int i = begin, j =2*i+1;                //i表示根,j表示左孩子
    while(j<=end){
        if(j+1<=end&&arr[j+1]>arr[j]) j++;  //如果有右孩子,取左右孩子中最大的那个
        if(arr[i]<arr[j]){                  //如果根小于孩子,那么交换并向下调整
            swap(arr[i],arr[j]);
            i = j;
            j = 2*i+1;
        } else {                            //如果不需要调整了则退出循环
            break;
        }
    }
}
vector<int> getMinKNumsByHeap(vector<int> arr,int k){
    //先建立一个大小为k的大根堆
    vector<int> kHeap(arr.begin(),arr.begin()+k);
    for(int i=k/2-1;i>=0;i--){              //从最后一个非叶子节点开始调整
        heapAdjust(kHeap,i,k-1);
    }
    for(int i=k;i<arr.size();i++){          //遍历所有的数组元素
        if(arr[i]<kHeap[0]){                //如果比堆顶元素小,那么放入堆并调整
            kHeap[0] = arr[i];
            heapAdjust(kHeap,0,k-1);
        }
    }
    return kHeap;                           //返回的堆便是数组中最小的k个元素
}

BFPRT算法

算法思想

  BFPRT算法在1973年由Blum、Floyd、Pratt和Tarjan联合发明,能够在时间复杂度O(N)内,从无序数组中找到第k小的数。如果想要求解最小的k个数字,那么遍历一遍数组即可。算法的核心便是如何找到第k小的数字,BFPRT采用的方法是基于快排划分的思路不断的缩小查找的范围。快排是基于分治的,而且划分通常使用一个随机的元素作为划分点。BFPRT算法采用了中位数作为划分点。
  1.找到区间内的中位数作为划分点;
  2.根据划分点进行划分,分为两个区间;
  3.根据划分点的位置判断第k小的数字在左右哪个区间内,然后递归处理对应的区间。
  其中,根据中位数寻找划分点的方法如下:
  1.把数组每5个元素分为一组,末尾不足5个也视为一组,对每组进行排序(一般使用插入排序),然后取中位数;
  2.将每组中位数组成的数组再进行划分,继续重复取中位数的操作,直到取出来只有一个数字,便是整个区间的中位数。

代码实现

// 获取区间内的中位数
int getMedian(vector<int> &arr,int begin, int end){
    //如果数组长度小于5,直接排序返回中位数的下标
    if(end-begin+1<=5){
        sort(arr.begin()+begin,arr.begin()+end+1);  //对每组进行插入排序,这里为了简单,直接用了sort
        return begin+(end-begin)/2;         
    }
    //将数组分成5个一组,对每一组进行排序,然后将每一组的中位数放到数组的前面
    for(int i=begin;i<=end;i+=5){
        int endI = i+4;
        endI = endI<end?endI:end;
        sort(arr.begin()+i,arr.begin()+endI+1);     //对每组进行插入排序,这里为了简单,直接用了sort
        swap(arr[i/5],arr[(i+endI)/2]);             //将每组的中位数放到数组的前面
    }
    //递归调用,求出中位数的中位数,最终只剩一个数,然后用于划分
    return getMedian(arr,begin,(end-1)/5);
}
int BFPRT(vector<int> &arr,int begin, int end, int k){
    if(begin==end) return arr[ begin ];               //递归边界,如果区间只剩一个元素
    int pivot = getMedian(arr,begin,end);           //获取划分点
    int i = begin, j = end;
    int tmp = arr[pivot];
    swap(arr[ begin ],arr[pivot]);
    while(i<j){
        while(i<j&&arr[j]>=tmp) j--;
        arr[i] = arr[j];
        while(i<j&&arr[i]<=tmp) i++;
        arr[j] = arr[i];
    }
    arr[i] = tmp;                                   //完成划分
    if(i==k) return arr[i];                       //如果刚好这个位置是k下标的位置,则返回
    else if(i>k) return BFPRT(arr,begin,i-1,k);   //如果在左侧,递归处理左侧
    else return BFPRT(arr,i+1,end,k);             //如果在右侧,递归处理右侧

}
vector<int> getMinKNumsByBFPRT(vector<int> arr,int begin, int end, int k){
    int minKth = BFPRT(arr,begin,end,k);          //找到第k+1小的数字,下标为k
    vector<int> res;
    for(int i=0;i<arr.size();i++){                //保留第k小的数字
        if(arr[i]<minKth){
            res.push_back(arr[i]);
        }
    }
    return res;
}

算法测试

  测试代码:

#include<bits/stdc++.h>
using namespace std;

// 此处省略以上的几个算法的代码

void printArray(vector<int> arr){
    for(int i=0;i<arr.size();i++){
        cout<<arr[i]<<" ";
    }
    cout<<endl;
}
int main(){
    const int SIZE = 15;
    srand(time(0));
    vector<int> arr;
    for(int i=0;i<SIZE;i++){
        arr.push_back(rand()%100);
    }
    cout<<"原数组为:"<<endl;
    printArray(arr);

    vector<int> kQuickSort = getMinKNumsByQuickSort(arr, 5);
    cout<<"快速排序法得到的前5小的数为:"<<endl;
    printArray(kQuickSort);

    vector<int> kHeap = getMinKNumsByHeap(arr,5);
    cout<<"使用大根堆获取最小的5个数为:"<<endl;
    printArray(kHeap);

    vector<int> kBFPRT = getMinKNumsByBFPRT(arr,0,arr.size()-1,5);
    cout<<"使用BFPRT算法获取最小的5个数为:"<<endl;
    printArray(kBFPRT);
    return 0;
}

  测试结果:

原数组为:
8 10 81 25 47 58 12 14 7 3 32 29 66 53 41
快速排序法得到的前5小的数为:
3 7 8 10 12
使用大根堆获取最小的5个数为:
12 10 8 7 3
使用BFPRT算法获取最小的5个数为:
8 3 7 10 12

当珍惜每一片时光~