(1) 请描述你解决这个问题的思路;
(2) 请给出主要的处理流程,算法,以及算法的复杂度。
方案 1:采用 trie 树,关键字域存该查询串出现的次数,没有出现为 0。最后用 10 个
元素的最小推来对出现频率进行排序。
关于此问题的详细解答,请参考此文的第 3.1 节:第三章续、Top K 算法问题的实现。
14. 一共有 N 个机器,每个机器上有 N 个数。每个机器最多存 O(N)个数并对它们操作。如
何找到 N^2 个数中的中数?
方案 1:先大体估计一下这些数的范围,比如这里假设这些数都是 32 位无符号整数(共
有 2 3̂2 个)。我们把 0 到 2 3̂2-1 的整数划分为 N 个范围段,每个段包含(2 3̂2)/N 个整
数。比如,第一个段位 0 到 2 3̂2/N-1,第二段为(2 3̂2)/N 到(2^32)/N-1,…,第 N 个
段为(2 3̂2)(N-1)/N 到 2 3̂2-1。然后,扫描每个机器上的 N 个数,把属于第一个区段的
数放到第一个机器上,属于第二个区段的数放到第二个机器上,…,属于第 N 个区段的数
放到第 N 个机器上。注意这个过程每个机器上存储的数应该是 O(N)的。下面我们依次统计
1