文件名称：请描述你解决这个问题的思路-introduction to 3d game programming with directx12 (龙书dx12版) pdf
文件大小：4.43MB
文件格式：PDF
更新时间：2024-06-23 16:10:37
微软面试 100题
(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)的。下面我们依次统计