算法通关村第11关【黄金】| 用4KB内存寻找重复元素-Toy模板网

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

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

思路：

直接用大小为32000的int数组来标记对应下标下的值出现次数，但是空间大小是32000*4B超过了4KB

这里采用一种压缩空间的方式——位图，每一位表示对应的一个整数，用32000位就能代表32000个整数，直接每个元素节省了一个int大小也就是4B的空间。

初始化数组时：this.bitset = new int[size >> 5] => 每32缩小一个int大小

set时：先获取pos除以32的整数部分，再获取pos除以32的余数

例如34，先34>>5等于1，再34&(11111)等于2（00010），对应bitset[1]中的第2位

bitset[0]对应1-32

bitset[1]对应33-64

这样就能每一个bitset用32位表示32个int文章来源地址https://www.toymoban.com/news/detail-703448.html

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

    class BitSet {
        int[] bitset;

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

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

        void set(int pos) {
            int wordNumber = (pos >> 5);
            int bitNumber = (pos & 0x1F);
            bitset[wordNumber] |= 1 << bitNumber;
        }
    }
}

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