寻求最大的k个数
方法一: 使用partition函数,将数组分为两组。
(1)分为两个组,sa和sb。
(2)若sa组的个数大于K,则继续在sa分组中找取最大的K个数字 。
(3)若sa组中的数字小于K ,其个数为T,则继续在sb中找取 K-T个数字 。
具体代码实现:
#include <iostream>
using namespace std ;
const int N = 8 ;
const int K = 4 ;
int partition(int a[] ,int low , int high)
{
int i = low - 1 ;
int j = low;
while(j < high)
{
if(a[j] >= a[high])
{
swap( a[i+1] , a[j]) ;
i++ ;
}
j++ ;
}
//最后处理a[high]
swap(a[i+1] , a[high]) ;
return i + 1;
}
int findk(int a[] , int low , int high , int k)
{
if(low < high)
{
int q = partition(a , low , high) ;
int len = q - low + 1 ; //表示第几个位置
if(len == k)
return q ; //返回第k个位置
else if(len < k)
return findk(a , q + 1 , high , k - len) ;
else
return findk(a , low , q - 1, k ) ;
}
}
int main()
{
int a[N] = {5 ,2 ,66 ,23, 11 ,1 ,4 ,55} ;
findk(a , 0 , N - 1 , K) ;
for(int i = 0 ; i < K ; i++)
cout<<a[i]<<endl ;
system("pause") ;
return 0 ;
}
方法二 :
此种方法为常用方法,建立一个大小为K的堆。每次遍历数组时,需要判断是否需要加入堆中。
堆中存储着的是最大的k个数字,但是若是需要插入堆中,则需要对堆进行调整时间为o(log k)。
全部的时间复杂度为o(n * log k)。
这种方法当数据量比较大的时候,比较方便。因为对所有的数据只会遍历一次,第一种方法则会多次遍历
数组。 如果所查找的k的数量比较大。可以考虑先求出k` ,然后再求出看k`+1 到 2 * k`之间的数字,然后
一次求取。
方法三:
利用二分的方法求取TOP k问题。
首先查找 max 和 min,然后计算出 mid = (max + min) / 2
该算法的实质是寻找最大的K个数中最小的一个。
代码如下:
#include <iostream>
using namespace std ;
const int N = 8 ;
const int K = 4 ;
/**//*
利用二分的方法求取TOP k问题。
首先查找 max 和 min,然后计算出 mid = (max + min) / 2
该算法的实质是寻找最大的K个数中最小的一个。
*/
int find(int * a , int x) //查询出大于或者等于x的元素个数
{
int sum = 0 ;
for(int i = 0 ; i < N ; i++ )
{
if(a[i] >= x)
sum++ ;
}
return sum ;
}
int getK(int * a , int max , int min) //最终max min之间只会存在一个或者多个相同的数字
{
while(max - min > 1) //max - min的值应该保证比两个最小的元素之差要小
{
int mid = (max + min) / 2 ;
int num = find(a , mid) ; //返回比mid大的数字个数
if(num >= K) //最大的k个数目都要比min值大
min = mid ;
else
max = mid ;
}
cout<<"end"<<endl;
return min ;
}
int main()
{
int a[N] = {54, 2 ,5 ,11 ,554 ,65 ,33 ,2} ;
int x = getK(a , 554 , 2) ;
cout<<x<<endl ;
getchar() ;
return 0 ;
}