该问题是这样的:
假如给你 20 亿个非负数的 int 型整数, 然后再给你一个非负数的 int 型整数 t , 让你判断 t 是否存在于这 20 亿数中, 你会怎么做呢?
有人可能会用一个 int 数组, 然后把 20 亿个数给存进去, 然后再循环遍历一下就可以了.
想一下, 这样的话, 时间复杂度是 O(n), 所需要的内存空间
4byte * 20 亿, 一共需要 80 亿个字节,
大概需要 8GB 的内存空间, 显然有些计算机的内存一次是加载不了这么这么多的数据的.
初步优化
按照上面的做法, 时间复杂度是 O(n), 内存是 8GB, 实际上我们是可以把时间复杂度降低到 O(1) 的.
例如我们可以这样来存数据, 把一个 int 非负整数 n 作为数组下标, 如果 n 存在, 则对应的值为 1, 如果不存在, 对应的值为 0. 例如数组 arr[n] = 1, 表示 n 存在, arr[n] = 0 表示 n 不存在.
那么, 我们就可以把 20 亿个数作为下标来存, 之后直接判断 arr[t] 的值, 如果 arr[t] = 1, 则代表存在, 如果 arr[t] = 0, 则代表不存在. 这样, 我们就可以把时间复杂度降低到 O(1). 不过空间复杂度我们并没有降低. 还稍微大了点.
由于 int 非负整数一共有 2^31 个, 所以数组的大小需要 2^32 这么大.
这里可能有人说也可以用 HashSet 来存啊, 时间复杂度也是近似 O(1). 不过这里需要说明的是, HashSet 里面存的必须是对象, 也就是说需要把 int 包装成 Integer, 显然一个对象的话是更花销内存的, 需要对象头啊什么的.....
再次优化
大家想一个问题, 对于一个数, 实际上我们只需要两种状态, 就是这个数存在和不存在这两种可能. 上面我们用 1 代表存在, 用 0 代表不存在.
也就是说, 我们是可以不用 int 型的数组来存储的, 一个 int 型占用 4 个字节, 即 32 个二进制位, 一共可以表示 40 亿多个状态. 用 int 型的来存两个状态, 多浪费.
所以我们可以考虑用 boolean 型的来存的, boolean 貌似就占用一个字节 (java 中的 boolena 貌似是占用一个字节). 而一个 boolean 有 true 和 false 两种状态, 所以也是成立的. 这样子的话占用的内存就是 2GB 的内存了.
这样, 就可以降低到之前的四分之 1 内存了.
最终优化: bitmap
大家再想一个问题, 虽然 boolean 是表示两种状态, 但是 boolean 实际上占用了 8bit 啊, 按道理 8bit 是可以表示 128 种状态的. 而被我们拿来表示两个状态, 是否也有点浪费了呢?
我们都知道, 一个二进制位, 有 0 和 1 两种状态, 所以说, 其实我们是可以用一个二进制位来代表一个 int 型的数是否存在的. 例如对于 1,3,5,7 这四个数, 如果存在的话, 则可以这样表示:
1 代表这个数存在, 0 代表不存在. 例如表中 01010101 代表 1,3,5,7 存在, 0,2,4,6 不存在.
那如果 8,10,14 也存在怎么存呢? 如图, 8,10,14 我们可以存在第二个字节里
以此类推. 这样子, 我们又可以把内存降低到之前的 8 分之一了.
这种采用一个二进制位来存储数据的方法, 我们也叫做 bitmap 算法.
可能有人会问, 假如我要添加一个数 n, 我知道它要存在第 n 个位那里, 把第 n 个二进制改为 1, 可是我要怎么操作呢?
这个对于 bitmap 算法是如何存储的, 如何进行增删操作的, 我会在之后的文章里讲.
Java 中有自带的 bitmap 实现, 今天我们就用 Java 中自带的 bitmap 来做道题练练手. 我们换道类似题目吧, 不知道你一眼是否就能想到用 bitmap 算法来做.
题目描述:
现在有五十亿个 int 类型的正整数, 要从中找出重复的数并返回.
判断 50 亿个数有哪些是重复和刚才上面那个判断是否存在, 其实是一样的. 我们采用 bitmap 算法来做. 不过这里 50 亿个数, 别人肯定是以文件流的形式给你的. 这样我们为了方便, 我们就假设这些数是以存在 int 型数组的形式给我们的.
代码如下:
- public class Test {
- // 为了方便, 假设数据是以数组的形式给我们的
- public static Set<Integer> test(int[] arr) {
- int j = 0;
- // 用来把重复的数返回, 存在 Set 里, 这样避免返回重复的数.
- Set<Integer> output = new HashSet<>();
- BitSet bitSet = new BitSet(Integer.MAX_VALUE);
- int i = 0;
- while (i <arr.length) {
- int value = arr[i];
- // 判断该数是否存在 bitSet 里
- if (bitSet.get(value)) {
- output.add(value);
- } else {
- bitSet.set(value, true);
- }
- i++;
- }
- return output;
- }
- // 测试
- public static void main(String[] args) {
- int[] t = {1,2,3,4,5,6,7,8,3,4};
- Set<Integer> t2 = test(t);
- System.out.println(t2);
- }
- }
打印结果:
[3, 4]
来源: https://www.cnblogs.com/kubidemanong/p/10147685.html