一:介绍
生活中经常会遇到求TopK的问题,在小数据量的情况下可以先将所有数据排序,最后进行遍历。但是在大数据量情况下,这种的时间复杂度最低的也就是O(NlogN)此处的N可能为10亿这么大的数字,时间复杂度过高,那么什么方法可以减少时间复杂度呢,以下几种方式,与大家分享。
二:局部淘汰法 -- 借助“冒泡排序”获取TopK
三:局部淘汰法 -- 借助数据结构"堆"获取TopK
import java.util.Arrays;
/**
* 通过堆这种数据结构
* 获得大数据量中的TopK
*/
public class TopKStack {
public static void main(String[] args) {
//定义一个数组,找出该数组中的topK,大数据量不好搞到,先用这个数组测试
int [] datas = {2,3,42,1,34,5,6,67,3,243,8,246,123,6,32,3451,23,5,6,31,5,6,2346,36};
int [] re = getTopK(datas,10);
System.out.println(Arrays.toString(re));
}
/**
* 获取前topk的方法
* @param datas 原数组
* @param num 前topNum
* @return 最后的topNum的堆数组
*/
static int[] getTopK(int[] datas,int num){
//定义存储前num个元素的数组,用于建堆
int[] res = new int[num];
//初始化数组
for (int i = 0; i < num; i++) {
res[i] = datas[i];
}
//建造初始化堆
for (int i = (num - 1)/2; i >= 0 ; i--) {
shift(res,i);
}
//遍历查找num个最大值
for (int i = num; i < datas.length; i++) {
if (datas[i] > res[0]){
res[0] = datas[i];
shift(res,0);
}
}
return res;
}
/**
* 调整元素满足堆结构
* @param datas
* @param index
* @return
*/
static int[] shift(int[] datas ,int index){
while(true){
int left = (index<<1) + 1; //左孩子
int right = (index<<1) + 2; //右孩子
int min_num = index; //标识自身节点和孩子节点中最小值的位置
//判断是否存在左右孩子,并且得到左右孩子和自身的最小值
if (left <= datas.length-1&&datas[left] < datas[index]){
min_num = left;
}
if (right <= datas.length-1&&datas[right] < datas[min_num]){
min_num = right;
}
//如果最小值不等于自身,则将最小值与自身交换
if (min_num != index){
int temp = datas[index];
datas[index] = datas[min_num];
datas[min_num] = temp;
}else{
//此处break是因为我们是从树的最下面进行调整的,如果上层节点符合堆,则下层节点一定符合!
break;
}
//执行到此处,说明可能需要调整下面的节点,则将初始节点赋值为最小值所在的节点位置,
// 因为最大值点的位置进行了交换,可能下层节点就不满足堆性质
index = min_num;
}
return datas;
}
}
四:分治法 -- 借助”快速排序“方法获取TopK
五:其他情况