Top K算法在不管是在日常的业务开发中，还是在大数据面试中都是非常非常非常常见的一个知识点，其实通俗一点来理解Top K算法也就是在一组数据中找出排名前K个的信息，比较常见的是推荐排名、积分排名、以及微博根据信息热度来排名，这些可以理解为是业务类型的场景，另外还有一些是面试中会问到的关于数据结构方面的知识点，那么在这里本文主要想通过实战的方式不同的维度来实现Top K算法!
常规Top K算法实现可以通过排序算法来实现，在这里我们 需要在一个无序的数组中找出前K个最大的元素，对这个这个问题采用常规的解题方式就是通过排序算法，具体的排序算法在这里就不多讲了，在这里我采用快排的方式，因为快排的时间复杂度在所有排序算法中是最低的(O(LogK))，通过快排的方式实现Top K最终的时间复杂度则是O(Logn+K)
基于快排的方式实现Top K算法：
public static void main(String[] args) {
int[] arr = {8,3,9,1,5,10,4,11};
int topN = 3;
int[] result = quickSort(arr,0,arr.length - 1);
System.out.println(Arrays.toString(result));
for(int i = 0 ;i < topN ; i++){ System.out.println(result[i]); } } public static int[] quickSort(int[] arr, int left, int right) { if (left < right) { int idx = partition(arr, left, right); quickSort(arr, left, idx - 1); quickSort(arr, idx + 1, right); } return arr; } private static int partition(int[] arr, int left, int right) { int pivot = left; int index = pivot + 1; for(int i = index; i <= right ; i++){ if(arr[i] > arr[pivot]){
swap(arr,i,index);
index++;
}
}
swap(arr,left,index - 1);
return index - 1;
}
public static void swap(int[] arr,int l,int r){
int temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
}
另外还有一种是基于堆来实现，通过堆结构我们可以维护一个小顶堆，然后顺序的进行遍历
PriorityQueue queue;
int maxHeapSize ;
public void topK(int k, int[] nums) {
queue = new PriorityQueue<>(k);
maxHeapSize=k;
if (k < nums.length) { for (int i = 0; i < k; i++) { queue.add(nums[i]); } for (int j = k; j < nums.length; j++) { if (nums[j] > queue.peek()) {
queue.poll();
queue.offer(nums[j]);
}
}
} else {
for (Integer integer : nums) {
queue.add(integer);
}
}
}
通过大数据技术实现Top K算法
通过Spark方式计算TopK算法就很简单了，代码如下：
val conf = new SparkConf().setAppName("TopK0")
val spark = new SparkContext(conf)
val textRDD = spark.textFile("hdfs://bigdatacluster/home/test/topk.txt")
textRDD.flatMap(line => line.split("="))
.map(word => (word, 1))
.reduceByKey(_ + _)
.map { pair => pair.swap }
.sortByKey(true, 2)
.top(10)
.foreach(println)
spark.stop()
TopK算法是在日常工作中和面试中都会遇到的问题，比较常考的就是堆外排序!