一、在2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数.
- 首先再2.5亿数字中进行去重，我们想和再0100内去重的做法是一致的，同时只要0100,101~200，...区域内都进行了去重后，那么整个2.5亿数字也就完成了去重。
- 首先将2.5数字进行分区，即把0-100,101-200...内的数值丢到对应的容器内，当然具体分割时容器可以很大，然后使用判断一个数字是否在容器内的常用算法bitmap进行判断。
- 局部去重完成，那么整体的去重也就完成了。
二、有5亿个int类型的数字，找它们的中位数。
-
首先理解中位数的概念就是将数据平均分为两半的位置的数字。
-
和上一题一样，我们先将数据遍历，分别落入不同的区域内，遍历时统计每一个分区数据的个数
-
首先中位数时中间的数，所以一定在中间的分区（这里分区时最好分为奇数分区），将左部分区内数据个数相加与右部分区内数据个数相加，就可以计算出中部分区中中位数应该时Topk,这是可以使用堆排序进行计算。求出Topk的值就是中位数。
-
方法2：同样需要做两遍统计，如果数据存在硬盘上，就需要读取2次。方法同基数排序有些像，开一个大小为65536的Int数组，第一遍读取，统计Int32的高16位的情况，也就是0-65535，都算作0；65536 - 131071都算作1。就相当于用该数除以65536。Int32 除以 65536的结果不会超过65536种情况，因此开一个长度为65536的数组计数就可以。每读取一个数，数组中对应的计数+1，考虑有负数的情况，需要将结果加32768后，记录在相应的数组内。
第一遍统计之后，遍历数组，逐个累加统计，看中位数处于哪个区间，比如处于区间k，那么0- k-1的区间里数字的数量sum应该<n/2（2.5亿）。而k+1 - 65535的计数和也<n/2，第二遍统计同上面的方法类似，但这次只统计处于区间k的情况，也就是说(x / 65536) + 32768 = k。统计只统计低16位的情况。并且利用刚才统计的sum，比如sum = 2.49亿，那么现在就是要在低16位里面找100万个数(2.5亿-2.49亿)。这次计数之后，再统计一下，看中位数所处的区间，最后将高位和低位组合一下就是结果了。
网友评论