TopK问题：什么是TopK问题？用堆和快排这两种方式来实现TopK |
您所在的位置：网站首页 › 二维数组topk › TopK问题：什么是TopK问题？用堆和快排这两种方式来实现TopK |
|
目录 一、什么是Top K问题 二、Top K的实际应用场景 三、Top K的代码实现及其效率对比 1.用堆来实现Top K 2.用快排来实现Top K 3.用堆或用快排来实现 TopK 的效率对比
正文 一、什么是Top K问题？ 给一个无序的数组，长度为N， 请输出最小 （或最大）的K个数。
二、Top K的实际应用场景 排行榜：用户数量有几百万， 但是只需要前100名的用户成绩。 要显示出来， 且这个排行榜是实时变化的。
三、Top K的代码实现 需求：给一个无序的数组，长度为N， 请输出最大的5个数。 1. 用堆来实现Top K——PriorityQueue（小顶堆） （1）步骤梳理： ①创建一个结点个数为 k 的小顶堆； ②当数据量 < k 时，将数据直接放到这个小顶堆中，此时堆的顶结点是最小值； ③当数据量 >= k时，每产生一个新数据都与堆的顶结点进行比较: 如果新数据 > 顶结点数据，则将顶结点删除，将新数据放到堆中，此时堆会进行排序，且维护了堆的总结点数为k; 如果新数据＜顶结点数据，则不动。 （2）中心思想：使堆的总结点数维持在 k 个。 （3）代码实现： 1 @Test 2 public void getTopKByHeapInsertTopKElement() { 3 int arrayLength = 10000000 + 10; 4 int topK = 5; 5 6 // 准备一个长度为arrayLength的无序数组： 7 int[] array = A03TopKByQuickSortAndNewArray.getDisorderlyArray(arrayLength); 8 9 // 准备一个总结点数为topK的小顶堆： 10 PriorityQueue heap = new PriorityQueue(topK); 11 12 long start = System.currentTimeMillis(); 13 14 // 始终维持一个总结点个数为k的堆： 15 insertButmaintainTheHeapAtTopK(heap, array, topK); 16 17 //获得最大topK： 18 printHeap(heap); 19 20 long end = System.currentTimeMillis(); 21 System.out.println("获得最大top5总耗时： " + (end - start)); 22 } 23 24 /** 25 * 用小顶堆来获取topK：当数据量超过topK后，新产生的数据直接和heap的顶结点进行比较。 26 */ 27 private static void insertButmaintainTheHeapAtTopK(PriorityQueue heap, int[] array, int topK) { 28 for (int i = 0; i < array.length; i++) { 29 if (i heap.peek()) { 33 heap.poll(); 34 heap.add(array[i]); 35 } 36 } 37 } 38 } 39 40 /** 41 * 获取最大TopK 42 * @param heap 43 */ 44 static void printHeap(PriorityQueue heap) { 45 Iterator iterator = heap.iterator(); 46 while (iterator.hasNext()) { 47 System.out.println(iterator.next()); 48 } 49 }
2. 用快排来实现Top K （1）步骤梳理： ①通过快排，先将无序数组array进行排序； ②取出最小Top 5，并放到topArray中；【关键】 ③超过arrayLength个数据后，又产生了insertNumber个新数据：直接和topArray数组比较，要放也是放到topArray中了；【关键】 （2）时间复杂度： ①排序的时间复杂度：O(N*logN)； ②取出top k的时间复杂度：O(1)，就是遍历数组。 （3）代码实现： 1 @Test 2 public void testGetTopKByQuickSortToNewArray() { 3 int topK = 5; 4 int arrayLength = 10000000; 5 6 //准备一个无序数组 7 int[] array = getDisorderlyArray(arrayLength); 8 9 long start = System.currentTimeMillis(); 10 11 //1.通过快排，先将无序数组array进行排序 12 quickSort(array, 0, array.length-1); 13 14 //2.取出最小Top 5，并放到topArray中： 15 int[] topKArray = insertToTopArrayFromDisorderlyArray(array, topK); 16 17 //3.超过arrayLength个数据后，又产生了insertNumber个新数据：直接和topArray[topKArray.length-1]比较，要放也是放到topArray中了 18 insertToTopKArray(topKArray, 10, 100, topKArray.length-1);//生成10个100以内的随机数作为新数据，和topKArray[topKArray.length-1] 19 20 long end = System.currentTimeMillis(); 21 System.out.println("获得最大top5总耗时： " + (end - start)); 22 } 23 24 /** 25 * 产生新的数据后，再和topKArray数组进行比较，看新数据时候需要插入到topKArray中，若需要插入，则堆topKArray进行重新快排。 26 * 27 * @param topKArray topK数组 28 * @param insertNumber 新产生的数据的个数 29 * @param randomIntRange 在什么范围内产生新数据，如生成10以内的随机数。 30 * @param topK 在topKArray中，确定要替换的元素的下标。获得最小topK，则topK是从小到大排序的topKArray的最后一个元素。 31 */ 32 private static void insertToTopKArray(int[] topKArray, int insertNumber, int randomIntRange, int topK) { 33 Random random = new Random(); 34 int randomInt; 35 for(int i = 0; i < insertNumber; i++) { 36 randomInt = random.nextInt(100); 37 if(randomInt < topKArray[topK]) {//新数据如果小于topArray[topK]，则直接用该数去替换topArray，然后再将topArray进行重新排序。 38 topKArray[topK] = randomInt; 39 quickSort(topKArray, 0, topKArray.length-1); 40 } 41 } 42 } 43 44 /** 45 * 从有序数组中取出需要的TopK，放到TopK数组中。 46 * 47 * @param sourceArray 有序数组 48 * @param topK 需要获取到Top K 49 * @return TopK数组 50 */ 51 private static int[] insertToTopArrayFromDisorderlyArray(int[] sourceArray, int topK) { 52 int[] topArray = new int[topK]; 53 for(int i = 0; i < 5; i++) { 54 topArray[i] = sourceArray[i]; 55 } 56 return topArray; 57 } 58 59 /** 60 * 快排 61 * @param target 62 * @param left 63 * @param right 64 */ 65 static void quickSort(int[] target, int left, int right) { 66 if (left >= right) { 67 return; 68 } 69 int pivot = target[left];// 基准点 70 int temp; 71 int i = left; 72 int j = right; 73 while (i = pivot && i |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |