算法通关村第十五关：青铜-用4KB内存寻找重复元素-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法通关村第十五关：青铜-用4KB内存寻找重复元素。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

青铜挑战-用4KB内存寻找重复元素

位运算在查找元素中的妙用

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

思路分析

本题是非常典型的海量数据处理的问题，使用的是位运算结构

内存大小关系
1字节 = 1byte（拜特） = 1B = 8bit（比特，位）
1KB = 1024B
1MB = 1024KB
1GB = 1024MB

如果没有内存要求，创建一个大小为N的数组，然后将这些整数（32位）放进来，N最大为32000，则需要 320004B ≈ 128KB
如果只有4KB的空间，那么只能寻址 4KB = 4*1024B = 4*10248bit（比特）该值大于32000
因此我们可以创建32000比特的位向量（比特数组），其中一个比特位置就代表一个整数，类似索引

利用这个位向量，就可以遍历访问整个数组。如果发现数组元素是v，那么就将位置为v的位设置为1，碰到重复元素，就输出一下

代码实现

1个数组元素存储 32 个数字信息，如索引为0的元素存储1~32文章来源地址https://www.toymoban.com/news/detail-695600.html

def check_duplicates(array):
    bitset = [0] * (32000 // 32)
    for num in array:
        num0 = num - 1
        if (bitset[num // 32] >> (num0 % 32)) & 1:
            print(num)
        else:
            bitset[num // 32] |= (1 << (num0 % 32))


if __name__ == '__main__':
    check_duplicates([1, 2, 3, 2])

public class FindDuplicatesIn32000 {
    public void checkDuplicates(int[] array) {
        BitSet bs = new BitSet(32000);
        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);
            }
        }

    }

    static 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;
        }
    }
}

到了这里，关于算法通关村第十五关：青铜-用4KB内存寻找重复元素的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！