如何在 40 亿个非负整数中找到出现两次的数和所有数的中位数

题目描述

使用最多 1GB 的内存,在 40 亿个无符号整数,找出所有出现两次的数。

思路分析

HashMap 来做词频统计显然是不行的,这里我们可以使用 bit 数组来统计数字出现的次数。

具体实现方式是这样的:

因为 32 位无符号整数的范围是 0~4 294 967 295

所以我们首先申请一个长度为 4294967295 * 2bit 数组 bitArray,大概是 80 亿个 bit,80 亿 / 8 == 10 亿字节,1GB 左右,满足内存空间的限制。

对于每一个数字,我们使用 bit 数组的两个位置来进行统计。

遍历这 40 亿个数:

  • 如果是第一次遇到 num,就把 bitArray[num * 2]bitArray[num * 2 + 1] 分别置为 0 和 1。表示 num 出现过一次。
  • 如果第二次再遍历到 num,也就是发现 bitArray[num * 2]bitArray[num * 2 + 1] 分别为 0 和 1,那么就将bitArray[num * 2]bitArray[num * 2 + 1] 分别置为 1 和 0。表示 num 出现过两次。
  • 如果第三次再遍历到 num,也就是发现 bitArray[num * 2]bitArray[num * 2 + 1] 分别为 1 和 0,那么就将bitArray[num * 2]bitArray[num * 2 + 1] 都置为 1 。表示 num 出现过两次以上。
  • 如果之后再遍历到 num,也就是发现 bitArray[num * 2]bitArray[num * 2 + 1] 都为 1,那么什么都不用做。

遍历完全部的数字之后,只需要遍历 bitArray,如果发现 bitArray[num * 2]bitArray[num * 2 + 1] 分别为 1 和 0。就证明 num 为只出现过两次的数。

完美解决。

进阶问题

使用最多 10MB 的内存,怎么找到这 40 亿个整数的中位数?

进阶问题分析

一大难题是内存被限制为 10 MB,用 bit 数组也没办法直接满足空间的要求。

所以我们需要使用分治的办法来分区间处理。

针对这个问题,我们将所有的数字划分区间,先确认中位数是在哪个区间内,再针对这个区间进行查找。

怎么划分区间?

首先要确定的是要划分多少个区间。保证用来统计区间的数组大小不能超过 10 MB

由于长度为 2MB 的无符号整型数组占用的空间为 8MB

所以将区间的数量定为 4 294 967 295 / 2M,向上取整为 2048 个区间。

第 0 区间为 0 ~ 2M - 1

第 1 区间为 2M ~ 4M - 1

……

第 i 区间为 2M × i ~ 2M ×(i+1)- 1

怎么确定中位数在哪个区间?

申请一个长度为 2048 的无符号整型数组 cnt,占用空间为 8MB,小于 10MB

cnt[i] 表示第 i 个区间内有多少个数。

然后遍历 40 亿个数,如果遍历到当前数为 num,先看 num 落在哪个区间上(num / 2M),然后进行 cnt[num / 2M]++ 操作。

这样遍历下来,就得到了每一个区间的数的分布状况,通过累加每个区间里的数字的出现次数(cnt[i]),就可以找到 40 亿个数的中位数(也就是第 20 亿个数)到底落在哪个区间上。

例如,0 ~ K-1 区间上数的个数为 18.88 亿,但是发现当加上第 K 个区间上数的个数之后就超过了 20 亿,那么可以知道第 20 亿个数一定是在第 K 个区间上,并且可以知道第 20 亿个数是第 K 个区间上的第 1.12 亿个数。

确定在哪个区间之后,怎么进一步确定是哪个数字?

方法也不难,我们继续申请一个长度为 2048 的无符号整型数组 array,占用空间 8 MB。然后遍历 40 亿个数,因为我们已经确定第 20 亿个数肯定在第 K 个区间中,所以这次只需要关注在第 K 个区间中的数(num / 2M == K),其他的数不用管。

遍历的时候如果遇到数字 num,就进行 [num - K * 2M]++ 操作。

当遍历完 40 亿个数之后,就得到了第 K 个区间的词频统计结果 array,在上面所举的例子中,我们只需要在第 K 个区间中找到第 1.12 亿个数即可。

发表回复

后才能评论