topn指的是从已经存在的数组中,找出最大(或最小)的前n个元素。
topn算法实现思路(找最大的n个元素)
1:取出数组的前n个元素,创建长度为n的最小堆。
2:从n开始循环数组的剩余元素,如果元素(a)比最小堆的根节点大,将a设置成最小堆的根节点,并让堆保持最小堆的特性。
3:循环完成后,最小堆中的所有元素就是需要找的最大的n个元素。
代码如下:
import java.util.Comparator;
/**
* 堆数据结构应用实例
*
* @author Administrator
*
*/
public class HeapApp {
public static int[] toPrimitive(Integer array[]) {
if (array == null)
return null;
if (array.length == 0)
return new int[0];
int result[] = new int[array.length];
for (int i = 0; i < array.length; i++)
result[i] = array[i].intValue();
return result;
}
/**
* 1:取出数组的前n个元素,创建长度为n的最小堆。
* 2:从n开始循环数组的剩余元素,如果元素(a)比最小堆的根节点大,将a设置成最小堆的根节点,并让堆保持最小堆的特性。
* 3:循环完成后,最小堆中的所有元素就是需要找的最大的n个元素。
*
* @param array
* @param n
* @return
*/
public static int[] topn(int[] array, int n) {
if (n >= array.length) {
return array;
}
Integer[] topn = new Integer[n];
for (int i = 0; i < topn.length; i++) {
topn[i] = array[i];
}
Heap<Integer> heap = new Heap<Integer>(topn, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
// 生成最大堆使用o1-o2,生成最小堆使用o2-o1
return o2 - o1;
}
});
for (int i = n; i < array.length; i++) {
int value = array[i];
int min = heap.root();
if (value > min) {
heap.setRoot(value);
}
}
// heap.sort();
return toPrimitive(topn);
}
public static void main(String[] args) {
int[] array = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 11, 9, 10, 100 };
array = new int[] { 101, 2, 3, 4, 5, 6, 7, 8, 11, 9, 10, 100 };
int[] result = topn(array, 5);
for (int integer : result) {
System.out.print(integer + ",");
}
}
}
分享到:
相关推荐
在大量的数据记录中,依据某可排序的记录属性(一般为数字类型),找出最大的前N个记录,称为 TopN问题。这是一个常常遇到的问题...本文对常见的TopN算法,进行分析比较,最后给出最优的TopN算法:基于小根堆的筛选 法.
一种缓解推荐偏好的协同过滤TopN算法.docx一种缓解推荐偏好的协同过滤TopN算法.docx一种缓解推荐偏好的协同过滤TopN算法.docx一种缓解推荐偏好的协同过滤TopN算法.docx一种缓解推荐偏好的协同过滤TopN算法.docx一种...
top N 算法,我只是转载,感谢原作者,求实严谨的态度,学习 http://blog.chinaunix.net/uid/20528042.html
基于用户多样性偏好的top-N推荐算法.pdf
Spark中实现MapReduce的TopN算法,分为唯一键TopN算法,非唯一键TopN算法和Group内的TopN算法
可以用于对任意数据类型进行topN排序,同时保持数据原来的序号或位置,在信息检索上非常使用,代码简单高效,使用简单。
一种基于PCBF的网络业务流量TopN测量算法,余烯键,,在高速网络流信息测量中对IP地址对应流量的Top-N的统计测量,具有开销大、处理速度慢等问题,在研究随机数据结构BF后,提出了一种新
基于正负反馈的SVM协同过滤Top-N推荐算法的介绍,通过本文档可以详细知道SVM原理
用模板类实现了小根堆,并在woniu_heap这个文件里的代码对小根堆进行了测试。其中push为插入一个元素到小根堆中,pop为删除小根堆的堆顶元素,top为取出根顶元素。
堆排序的c++实现,heap[]定义为泛型
为解决上述问题,提出了基于用户谱聚类的Top-N协同过滤推荐算法(SC-CF),即应用谱聚类将兴趣相似的用户分成一类,具有相似兴趣爱好的用户比其他用户具有更高的推荐参考价值,然后在类中为目标用户推荐。SC-CF 算法...
topn算法的堆实现,即从大量数据中寻找最大或最小的N个数
欢迎多多交流 ps:按照书中伪码写成,元素由1开始,故数组中第一位A[0]为填充,并不算... //交换堆的第一个元素和堆的最后一个元素 A[i] = A[1]; A[1] = temp; i--; //堆的大小减一 MaxHeapIfy(A, i, 1); //调堆 }
【题目】内存中的行列结构的数据集,存在主键 k,求 TopN 算法 上述题目在多核环境下的优化 数据集大小为 1TB,分布规律未知。存储在某存储服务上,以 get(min_k, max_k) 接口获取数据,求多台服务器的计算方案 原题...
空时自适应算法的源代码,MountainTop数据可以从网上免费下载,这个MATLAB源代码实现了对该数据的处理,我课程设计的一部分。
TOPN.pbix DAX中很实用的表函数:TOPN,返回表的前N行,是非重复的行哦
详细介绍tableau topN的实现方法,对于TOP N以外的值汇总为“其它”项。
hive不直接支持分组取TopN的操作,需要自定义udf函数打成jar包添加到hive运行环境中
该代码为TOPK算法的Hash实现,简要说明请见博客http://blog.csdn.net/yankai0219/article/details/8185872
一个基于粒子群算法挖掘top-1频繁项的算法