算法通过村第十一关黄金挑战——位运算如何实现压缩储存

大家好，我是怒码少年小码。

由于现在处于备赛阶段，接下来我写的代码都将使用Java语言。

用 4 KB 内存寻找重复元素

题目要求：给定一个数组，包含从1到N的整数，N最大为32000，数组可能还有重复值，且N的取值不定，若只有4KB的内存可用，该如何打印数组中所有重复元素。

分析：本身是一道海量数据问题的热身题，如果去掉“只有4KB”的要求，我们可以先创建一个大小为N的数组，然后将这些数据放进来，但是这里数组最大为32KB，而题目有4KB的内存限制，我们就必须先确定该如何存放这个数组。
如果只有4KB的空间，那么只能寻址842^10个比特，这个值比32000要大的，因此我们可以创建32000比特的位向量(比特数组)，其中一个比特位置就代表一个整数。
利用这个位向量，就可以遍历访问整个数组。如果发现数组元素是v，那么就将位置为v的设置为1，碰到重复元素，就输出一下。

public class FindDuplicates32000{
    public void checkDuplicates(int[] array) {
        BitSet bs = new BitSet(320000);
        for (int i = 0; i < array.length; i++) {
            int num = array[i];
            int num0 = num - 1;
            if (bs.get(num0)) {
                System.out.println(num);
            } else {
                bs.set(num0);
            }
        }
    }
    class BitSet {
        int[] bitset;

        public BitSet(int size) {
            this.bitset = new int[size >> 5];
        }

        boolean get(int pos) {
            int wordNumber = (pos >> 5);//除以32
            int bitNumber = (pos & 0x1F);//取模32
            return (bitset[wordNumber] & (1 << bitNumber)) != 0;
        }

        void set(int pos) {
            int wordNumber = (pos >> 5);//除以32
            int bitNumber = (pos & 0x1F);//取模32
            bitset[wordNumber] |= 1 << bitNumber;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

这段代码定义了一个名为FindDuplicates32000的类，它包含一个名为checkDuplicates的方法，该方法用于查找数组中的重复元素。这个方法使用位集数据结构来查找和跟踪数组中的每个数字的索引。下面是对这段代码的详细解释：

• public class FindDuplicates32000：这是一个名为FindDuplicates32000的公共类。
• public void checkDuplicates(int[] array)：这是一个公共方法，名为checkDuplicates，它接受一个整数数组作为参数。
• BitSet bs = new BitSet(320000);：创建一个新的位集对象bs，大小为320000位。
• for (int i = 0; i < array.length; i++) {...}：这是一个循环，用于遍历输入数组。
• int num = array[i];：从输入数组中获取当前元素的值。
• int num0 = num - 1;：计算当前元素的索引的前一个值。
• if (bs.get(num0)) {...}：检查位集是否已经标记了当前元素的索引的前一个值。如果是，则输出当前元素的值。
• else {bs.set(num0);}：如果位集没有标记当前元素的索引的前一个值，则将其标记。
• class BitSet {...}：这是一个内部类，表示位集数据结构。它包含两个方法：get和set，分别用于获取和设置位集中的位。
• boolean get(int pos)：此方法返回位集中的特定位置是否已被标记。
• void set(int pos)：此方法将位集中的特定位置标记为已标记。

主要作用是查找并输出数组中的重复元素。它使用位集数据结构来跟踪每个元素的索引，以便在遍历数组时可以快速检查某个元素是否已经被标记过。如果某个元素已经被标记过，那么它就是重复的元素，会被输出。

代码不要求会自己写，但是一定要看得懂。

END

本篇的参考博文：https://juejin.cn/post/7281159113881501715