本文共 782 字，大约阅读时间需要 2 分钟。
问题A：
数组值范围0～N，找出一个即可：位置交换，时间O(N)，空间O(1)
问题B：
数组值范围0～N，使用辅助空间二分范围，时间O(NlogN)，空间O(1)
问题C：
数组值范围不限哈希，时间O(N)，空间O(N)
问题D：
数组值不限，对空间要求严格排序，时间O(NlogN)，空间O(1)
问题E：
对空间要求严格 数组巨大 例如上百亿url链接黑名单过滤绝对优秀的哈希函数，上百亿大小比特表
缺点，找不到如此优秀哈希函数，且扩展不容易布隆过滤器，容忍一定程度失误率
k个哈希函数，m长度比特表，m通常大于N问题F：
20亿个数字中，找出现次数最多的数：将20亿个数，拆分成多个批次处理，每次保留上个批次最多的数字，参与下个批次的计算。
问题G：
40亿个非负数，找到未出现过的数：bitmap方法，一个位表示对应数字是否出现。
分桶，将40亿区间划分几个，统计每个桶内的数字，若数字数量小于区间宽度，则一定有未出现数。问题H：
100亿个url找出所有重复url：哈希分流，用哈希函数将所有url分配至不同服务器，利用哈希函数特性，不同服务器url一定不同。
100亿个url找重复topK：
哈希分流后，每个服务器保持一个小根堆，然后所有服务器统一计算，生成唯一一个K大小的小根堆，这里可以使用外排序。
问题I：
40亿个非负正数中找到出现2次的数：bitmap，每两个bit统计一个数出现的次数。
问题J：
40亿个数找中位数：分桶计数，找到最中间区间，递归处理。
–
问题K：
找数组中重复次数大于N/K的数：哈希，时间O(N*K)，空间O(K)
哈希维护k-1个数（num，times），保存k-1个不同的数，当第k个不同的数找到时，所有k个数times-1，然后继续找k个不同的数，遍历完毕后，哈希表里即为所求。
转载地址：http://zbwji.baihongyu.com/