韩国有哪些做潮牌的网站,泰安网络软件公司,如何去掉Wordpress访问网站,黄页88推广效果怎么样目录 题目#xff1a;用4KB内存寻找重复元素思路分析#xff1a;使用位存储如何存储这32000个整数#xff1f;每个整数对应在位图中的存储状态举例如何判断是重复的#xff1f;具体的步骤 复杂度#xff1a;时间复杂度 O ( n ) O(n) O(n)、空间复杂度 O ( 1 ) O(1) O(1)Go… 目录 题目用4KB内存寻找重复元素思路分析使用位存储如何存储这32000个整数每个整数对应在位图中的存储状态举例如何判断是重复的具体的步骤 复杂度时间复杂度 O ( n ) O(n) O(n)、空间复杂度 O ( 1 ) O(1) O(1)Go代码 在海量数据中此时普通的数组、链表、Hash、树等等结构有无效了 因为内存空间放不下了。而常规的递归、排序回溯、贪心和动态规划等思想也无效了因为执行都会超时必须另外想办法。这类问题该如何下手呢这里介绍三种非常典型的思路 使用位存储使用位存储最大的好处是占用的空间是简单存整数的1/8。例如一个40亿的整数数组如果用整数存储需要16GB左右的空间而如果使用位存储就可以用2GB的空间这样很多问题就能够解决了。 如果文件实在太大 无法在内存中放下则需要考虑将大文件分成若干小块先处理每个块最后再逐步得到想要的结果这种方式也叫做外部排序。这样需要遍历全部序列至少两次是典型的用时间换空间的方法。 堆如果在超大数据中找第K大、第K小K个最大、K个最小则特别适合使用堆来做。而且将超大数据换成流数据也可以而且几乎是唯一的方式口诀就是“查小用大堆查大用小堆”。 常识补充10亿 ≈ 1G、100万 ≈ 1M 题目用4KB内存寻找重复元素
给定一个数组包含从1到N的整数N最大为32000数组可能还有重复值且N的取值不定若只有4KB的内存可用该如何打印数组中所有重复元素。
思路分析使用位存储
如何存储这32000个整数
常规思路分析32000个整数整数用int表示一个int占用4个字节(byte)32000个整数所需内存就是
32000 * 4 128000byte
32000 * 4 / 1024 125KB
125KB 4KB //可见已经超过题目要求的4KB内存要求。下面我们使用位存储的方式1个字节(byte)8位(bit)32000个正数用32000个位就是
32000 / 8 4000byte
32000 / 8 / 1024 3.9KB
3.9KB 4KB //如此就满足题意使用了4KB就能存储32000个元素每个整数对应在位图中的存储状态举例
原数据 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ...
该值在位图中的索引值 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 2 2 2 ...
该值在位图中的偏移量 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 ...1 对应的位图值和二进制值为byteMap[0] 00000010
2 对应的位图值和二进制值为byteMap[0] 00000100
3 对应的位图值和二进制值为byteMap[0] 00001000
4 对应的位图值和二进制值为byteMap[0] 00010000
5 对应的位图值和二进制值为byteMap[0] 00100000
6 对应的位图值和二进制值为byteMap[0] 01000000
7 对应的位图值和二进制值为byteMap[0] 10000000
8 对应的位图值和二进制值为byteMap[1] 00000001
9 对应的位图值和二进制值为byteMap[1] 00000010
...如何判断是重复的
既然我们用一个位(bit)代表一个数值那么该位的两种状态0或1就可以用于判断该值是否存在。 例如字节00001101表示以下情况
第 0 位最低位为 1表示数字 1 出现过。第 1 位为 0表示数字 2 没有出现过。第 2 位为 1表示数字 3 出现过。第 3 位为 1表示数字 4 出现过。后续位为 0表示数字 5 到 8 都没有出现过。
mark : 1 offset //offset 就是偏移量
if (bitmap[index] mask) ! 0 {// 位已经被设置说明数字出现过
}
bitmap[index] | mask //设置该位值为1具体的步骤 位图Bitmap是一种数据结构用于表示一组元素的状态或属性通常用二进制位来表示每个位代表一种状态或属性。在计算机科学中位图被广泛用于各种应用如图像处理、数据压缩、数据库索引等。 初始化位图由于N最大是32000可以是哦用一个长度为32000/84000的位图每个位可以表示一个整数。遍历数组对于数组中的每个元素 计算x在位图中的索引和位偏移。例如x5则索引为5/80位偏移为5%85。检查位图的索引位置是否已经被标记。 如果未被标记则将其标记为已访问如果已经被标记则说明x是重复的打印x。 打印重复元素。
复杂度时间复杂度 O ( n ) O(n) O(n)、空间复杂度 O ( 1 ) O(1) O(1)
Go代码
源码地址 GitHub-golang版本含单元测试代码
func FindDuplicatesIn32000(arr []int) (duplicate []int) {N : 32000bitmap : make([]byte, N/81)for _, num : range arr {// 计算 num 在 bitmap 中的索引// index : num / 8index : num 3// 计算 num 在 bitmap 中的偏移量offset : num % 8mark : byte(1 offset)if bitmap[index]mark ! 0 {duplicate append(duplicate, num)} else {bitmap[index] | mark}}return
}或者
func FindDuplicatesIn32000(arr []int) (duplicate []int) {N : 32000// 或者这里不用1只要索引是base0的即可bitmap : make([]int, N/32)for _, num : range arr {num0 : num - 1 //base0开始index : num0 / 32offset : num0 % 32mark : 1 offsetif bitmap[index]mark ! 0 {duplicate append(duplicate, num)} else {bitmap[index] | mark}}return
}
