典型的Top K算法 找出一个数组里面前K个最大数.doc

典型的Top K算法 找出一个数组里面前K个最大数 Top K算法是解决一个经典的问题，即在一个大规模的数组中找到前K个最大数的问题。在这个问题中，我们需要在一个数组中找到前K个最大数，例如在搜索引擎中，需要找出最热门的10个查询串。下面我们将详细地介绍Top K算法的解决方案。 哈希表 哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。哈希表的做法其实很简单，就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。 问题解析 要统计最热门查询，首先就是要统计每个Query出现的次数，然后根据统计结果，找出Top 10。所以我们可以基于这个思路分两步来设计该算法，即： 第一步：Query统计 Query统计有以下两个方法可供选择： 1. 直接排序法 直接排序法是最先想到的算法，首先对这个日志里面的所有Query都进行排序，然后再遍历排好序的Query，统计每个Query出现的次数。但是题目中有明确要求，那就是内存不能超过1G，一千万条记录，每条记录是255Byte，很显然要占据2.375G内存，这个条件就不满足要求了。 2. Hash Table 法 Hash Table法统计字符串出现的次数非常好。在这里，我们可以考虑把他们都放进内存中去，而现在只是需要一个合适的数据结构，在这里，Hash Table绝对是我们优先的选择，因为Hash Table的查询速度非常的快，几乎是O(1)的时间复杂度。 第二步：找出Top 10 找出出现次数最多的10个Query。 算法一：普通排序 我们只用找出Top 10，所以全部排序有冗余。 算法二：Heap排序 Heap排序是解决Top K问题的常用方法，我们可以使用Heap来存储Top K个元素，然后不断地将新的元素与Heap的根节点进行比较，如果新的元素比Heap的根节点更大，那么就将新的元素加入Heap中，并将Heap的根节点删除。这样我们就可以找到Top K个最大数。 Top K算法可以使用Hash Table和Heap排序来解决问题。Hash Table可以快速地统计Query出现的次数，而Heap排序可以快速地找出Top K个最大数。