算法通过村第十一关黄金挑战——位运算如何实现压缩储存

编程入门 行业动态 更新时间:2024-10-15 12:30:01

<a href=https://www.elefans.com/category/jswz/34/1770096.html style=算法通过村第十一关黄金挑战——位运算如何实现压缩储存"/>

算法通过村第十一关黄金挑战——位运算如何实现压缩储存

大家好,我是怒码少年小码。

由于现在处于备赛阶段,接下来我写的代码都将使用Java语言。

用 4 KB 内存寻找重复元素

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

分析:本身是一道海量数据问题的热身题,如果去掉“只有4KB”的要求,我们可以先创建一个大小为N的数组,然后将这些数据放进来,但是这里数组最大为32KB,而题目有4KB的内存限制,我们就必须先确定该如何存放这个数组。
如果只有4KB的空间,那么只能寻址842^10个比特,这个值比32000要大的,因此我们可以创建32000比特的位向量(比特数组),其中一个比特位置就代表一个整数。
利用这个位向量,就可以遍历访问整个数组。如果发现数组元素是v,那么就将位置为v的设置为1,碰到重复元素,就输出一下。

public class FindDuplicates32000{public void checkDuplicates(int[] array) {BitSet bs = new BitSet(320000);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);//除以32int bitNumber = (pos & 0x1F);//取模32return (bitset[wordNumber] & (1 << bitNumber)) != 0;}void set(int pos) {int wordNumber = (pos >> 5);//除以32int bitNumber = (pos & 0x1F);//取模32bitset[wordNumber] |= 1 << bitNumber;}}
}

这段代码定义了一个名为FindDuplicates32000的类,它包含一个名为checkDuplicates的方法,该方法用于查找数组中的重复元素。这个方法使用位集数据结构来查找和跟踪数组中的每个数字的索引。下面是对这段代码的详细解释:

  • public class FindDuplicates32000:这是一个名为FindDuplicates32000的公共类。
  • public void checkDuplicates(int[] array):这是一个公共方法,名为checkDuplicates,它接受一个整数数组作为参数。
  • BitSet bs = new BitSet(320000);:创建一个新的位集对象bs,大小为320000位。
  • for (int i = 0; i < array.length; i++) {...}:这是一个循环,用于遍历输入数组。
  • int num = array[i];:从输入数组中获取当前元素的值。
  • int num0 = num - 1;:计算当前元素的索引的前一个值。
  • if (bs.get(num0)) {...}:检查位集是否已经标记了当前元素的索引的前一个值。如果是,则输出当前元素的值。
  • else {bs.set(num0);}:如果位集没有标记当前元素的索引的前一个值,则将其标记。
  • class BitSet {...}:这是一个内部类,表示位集数据结构。它包含两个方法:getset,分别用于获取和设置位集中的位。
  • boolean get(int pos):此方法返回位集中的特定位置是否已被标记。
  • void set(int pos):此方法将位集中的特定位置标记为已标记。

主要作用是查找并输出数组中的重复元素。它使用位集数据结构来跟踪每个元素的索引,以便在遍历数组时可以快速检查某个元素是否已经被标记过。如果某个元素已经被标记过,那么它就是重复的元素,会被输出。

代码不要求会自己写,但是一定要看得懂。

END

本篇的参考博文:

更多推荐

算法通过村第十一关黄金挑战——位运算如何实现压缩储存

本文发布于:2023-12-03 16:46:20,感谢您对本站的认可!
本文链接:https://www.elefans.com/category/jswz/34/1656729.html
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。
本文标签:算法   如何实现   黄金   一关

发布评论

评论列表 (有 0 条评论)
草根站长

>www.elefans.com

编程频道|电子爱好者 - 技术资讯及电子产品介绍!