算法通关村——位运算在查找重复元素中的妙用

这篇具有很好参考价值的文章主要介绍了算法通关村——位运算在查找重复元素中的妙用。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

用4KB内存寻找重复元素

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

如果不要求使用4KB,最简单就是使用N长的数组然后将元素都存入数组,再打印,但是题目规定了4KB,很显然这种做法就不大行了,一定会超出时间限制。

4KB=4 * 8 * 2 ^ 10 比特,这个值是大于32000,可以使用比特数组来存储相应的元素。利用这个位向量,就可以遍历访问整个数组。如果发现数组元素是v,那么就将位置为v的设置为1,碰到重复元素,就输出。代码就没什么可说的,真要实现起来,还是有一点复杂的。文章来源地址https://www.toymoban.com/news/detail-683757.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);//除以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;
        }
    }
}

到了这里,关于算法通关村——位运算在查找重复元素中的妙用的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法通关村——二分查找在二叉树中的应用

    二叉搜索树中的搜索 给定二叉搜索树(BST)的根节点 root 和一个整数值 val。 你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 null 。 一开始以为很难,无从下手,但是题目已经规定了这是二叉搜索树,意味着将元素按照中序排

    2024年02月13日
    浏览(38)
  • 算法第四十一天-排除排序链表中的重复元素Ⅱ

    题意:在一个 有序 链表中,如果一个节点的值出现不止一次,那么把这个节点删除掉 重点: 有序链表 ,所以,一个节点的值出现不止一次,那么他们必相邻。 方法一:递归 链表和树的问题,一般都可以有递归和迭代两种写法。对于本题一定要记住是有序链表,值相同的节

    2024年04月11日
    浏览(97)
  • 算法leetcode|83. 删除排序链表中的重复元素(rust重拳出击)

    给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 链表中节点数目在范围 [0, 300] 内 -100 = Node.val = 100 题目数据保证链表已经按升序 排列 面对这道算法题目,二当家的再次陷入了沉思。 本来要删除重复元素,需要两次遍

    2024年02月07日
    浏览(42)
  • 算法leetcode|82. 删除排序链表中的重复元素 II(rust重拳出击)

    给定一个已排序的链表的头 head , 删除原始链表中所有重复数字的节点,只留下不同的数字 。返回 已排序的链表 。 链表中节点数目在范围 [0, 300] 内 -100 = Node.val = 100 题目数据保证链表已经按升序 排列 面对这道算法题目,二当家的再次陷入了沉思。 这道题目和 83. 删除排序

    2024年02月08日
    浏览(38)
  • 算法每日一题: 删除排序列表中的重复元素2 | 循环 | 链表的删除 | 虚拟节点

    大家好,我是星恒 今天的题目是昨天题目的进化题,他对链表的删除加深了理解。最重要的是学会了对循环中的特殊部分的处理,还有设置虚拟节点的情况 好了,话不多说,我们直接开始 题目:leetcode 82 给定一个已排序的链表的头 head , 删除原始链表中所有重复数字的节点

    2024年01月16日
    浏览(39)
  • 算法通关村——透彻理解二分查找

    假设现在有个数组里面有重复元素,并且按照增序排列,如果有相同元素,返回最左侧的第一个重复元素的位置。 核心思路也是比较简单了,当找到第一个重复的元素时候,记录位置,然后向左移动,左边的不是目标元素,就意味着左边没有重复的目标元素,然后+1就是目标

    2024年02月13日
    浏览(33)
  • 算法通关村——删除元素专题

    LeetCode27.给你一个数组nums和一个值val,你需要原地移除所有数值等于val的元素,并返回移除后数组的新长度。要求:不要使用额外的数组空间,你必须仅使用  O(1)  额外空间并  原地 修改输入数组 。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 示例

    2024年02月13日
    浏览(38)
  • 算法通关村十一关 | 位运算实现加法和乘法

    在计算机中,位运算的效率要比加减乘除的效率更高,因此在高性能软件中源码中大量使用,计算机里各种运算基本上都是位运算。 学习下面内容之前建议先学习位运算规则:算法通关村十一关 | 位运算的规则_我爱学算法的博客-CSDN博客 题目: LeetCode371 给你两个整数a和b,

    2024年02月11日
    浏览(48)
  • 算法通关村第十四关——解析堆在数组中找第K大的元素的应用

    力扣215题 , 给定整数数组nums和整数k,请返回数组中第k个最大的元素。 请注意,你需要找的是数组排序后的第k个最大的元素,而不是第k个不同的元素。 分析 :按照“找最大用小堆,找最小用大堆,找中间用两个堆”,这道题用最小堆来解决,构造一个大小只有K的最小堆

    2024年02月07日
    浏览(38)
  • (78)删除有序数组中的重复项(79)排序矩阵查找

    水晶帘动微风起,满架蔷薇一院香。 —高骈- 题目链接:删除有序数组中的重复项 给你一个 非严格递增排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个

    2024年04月17日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包