无锡网站制作工具,苏州网站制作网络建设公司,自己做网站nas,网站开发公司需要那些硬件设备青铜挑战-用4KB内存寻找重复元素
位运算在查找元素中的妙用
题目要求#xff1a; 给定一个数组#xff0c;包含从1到N的整数#xff0c;N最大为32000#xff0c;数组可能还有重复值#xff0c;且N的取值不定#xff0c;若只有4KB的内存可用#xff0c;该如何打印数组中…青铜挑战-用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
def check_duplicates(array):bitset [0] * (32000 // 32)for num in array:num0 num - 1if (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);// 除以32int bitNumber (pos 0x1F); // 求32的余数return (bitset[wordNumber] (1 bitNumber)) ! 0;}void set(int pos) {int wordNumber (pos 5);// 除以32int bitNumber (pos 0x1F);// 求32的余数bitset[wordNumber] | 1 bitNumber;}}
}
