关于我的 Leetcode 题目解答，代码前往 Github：https://github.com/chenxiangcyr/leetcode-answers
适用范围：求第 k 大，中位数，不重复或重复的数字，且元素范围很大，不能一次载入内存。
基本原理：通过多次划分，逐步确定范围，然后最后在一个可以接受的范围内进行。
问题1：在2.5亿个整数中找出不重复的整数的个数。假设内存不足以同时容纳2.5亿个整数。
-
方案1：
整数个数为 2^32，也就是，我们可以将这 2^32 个数，划分为 2^8 个区域（比如2^8 个文件），然后将数据分离到不同的区域，然后不同的区域在利用 bitmap 就可以直接解决了。 -
方案2：
采用 2-bitmap，每个数分别 2 个bit，00 表示出现 0 次，01 表示出现 1 次，11 表示出现多次。
需要内存2.5 亿 * 2 = 5亿 bit = 0.5G bit = 0.07G byte = 70M。
依次扫描2.5亿个整数：- 00 变 01
- 01 变 11
- 10 不变
问题2：在5亿个整数中找出中位数。
- 方案1：将这些数字划分到 2^16 个区域，依次统计每个区域内元素的个数，根据统计结果，判断出中位数位于哪个区域。随后在重新扫描该区域。
网友评论