Bitmap 去重(JAVA)

Bitmap 去重是指，当给定一个数组 A，其取值范围为 [0, n)，可采用 floor((n+7)/8) 个字节长度的 bitmap 对该数组去重。bitmap 初始化为全 0，计算过程中逐个处理数组 A 的元素，以 A 中元素取值作为 bitmap 的下标，将该下标的 bit 置 1，最后统计 bitmap 中 1 的个数即为数组 A 的 count distinct 结果。

以下是用Java语言模拟Bitmap去重的代码：

public class Bitmap {
    private byte[] bitmap;

    public Bitmap(int n) {
        int byteSize = (n + 7) / 8;
        bitmap = new byte[byteSize];
    }

    public void set(int value) {
        int byteIndex = value / 8;
        int bitIndex = value % 8;
        byte mask = (byte) (1 << bitIndex);
        bitmap[byteIndex] |= mask;
    }

    public int countDistinct(int[] array) {
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            int value = array[i];
            int byteIndex = value / 8;
            int bitIndex = value % 8;
            byte mask = (byte) (1 << bitIndex);
            if ((bitmap[byteIndex] & mask) == 0) {
                count++;
                bitmap[byteIndex] |= mask;
            }
        }
        return count;
    }
}

使用方法如下：

int[] array = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5};
Bitmap bitmap = new Bitmap(array.length);
int count = bitmap.countDistinct(array);
System.out.println(count); // 输出 10

这段代码首先创建了一个Bitmap对象，初始化时传入数组A的取值范围n。然后通过set方法将bitmap中对应的bit设置为1。最后通过countDistinct方法统计bitmap中1的个数，即为数组A的去重个数。