找无序数组中最小的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
Comments | NOTHING