首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

C++】位图

这种情况,我们就可以用到今天的主角—— 位图 。 给定的每个整形只有两种状态:在与不在,我们完全可以通过一个比特位的0和1来记录每个数字在不在。...---- 一、概念 所谓位图,就是用每一位来存放某种状态,适用于海量数据,数据无重复的场景。通常是用 来判断某个数据存不存在的。...由于用连续的两个比特位来记录会比较麻烦,我们可以开两个位图,各用一位来记录高位和地位。 这样就能复用我们的bitset了。 ...思路也很简单,我们开两个位图,如果两个位图中的某一位同时为1,那么就是两个文件的交集。 注意:虽然是100亿个整数,但是整形最大范围还是42亿多,所以是不需要开100亿个空间的。 3....位图应用变形:1个文件有100亿个int,1G内存,设计算法找到出现次数不超过2次的所有整 数 其实和第一题的解法一样,只不过现在需要多加一种状态,那就是超过2次的我们标记为:11。

35030
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    C++位图

    先按位取反原来的位图,再把原来的位图与取反的位图按位与,若存在1则为非0,为真返回true;若不存在则没有1全0,为假,返回false;bool Test(size_t x)//判断x是否在这堆数里面{...把文件1的数据放进位图1,把文件2的数据放进位图2,然后逐个遍历位图1的数据同时遍历位图2。当两个位图的数据的标记位都是1时,说明该数据即存在文件1也存在文件2,这个数据就是两个文件的交集。...逐个遍历两个位图,找出相同的数据即可。...bs2.Test(x))//两个位图都是0---数据出现0次{//00->01bs2.Set(x);}else if (!...bs1.Test(x) && bs2.Test(x))//第一个位图是1,第二个位图是0---数据出现1次{//01->10bs1.Set(x);bs2.ReSet(x);}else //两个位图都是1

    45520

    C++ 哈希的应用【位图

    了 ---- 2、位图概念 位图 是个啥?...,就这点内存占用,随便给(某鹅厂应用占用内存随便都是几百兆) 位图的工作原理 在 C++ 中提供了位图结构 bitset(需要包含头文件 ) ---- 3、位图的模拟实现 注...在 C语言 阶段,我们学习过一个知识点:大小端字节序,对于多字节的数据类型,诸如 int 存在大小端问题,比如 int a = 1 在大端机器中为:00 00 00 01 而在小端机器中为:01 00...,并且大小都为 100 亿,总占用约 2.4 GB 的内存空间 解题思路:二进制,我们把 位图1 看作高位,位图2 看作低位,第一次出现时,给 位图2 进行设置,后续第二次乃至第N次出现时,重置 位图2...字符串等数据无法做到很好的映射 映射字符串时,主要是无法确保唯一性,但可以判断字符串 是否存在,这就是 哈希 的另一个应用场景:布隆过滤器 弗雷尔卓德之心 布隆 ---- 总结 以上就是本次关于 C+

    28930

    C++】哈希的应用 -- 位图

    _bs[i] & (1 << j); } private: vector _bs; }; } 其中,模板参数 N 是给定的 数据的范围 (特别注意这里N不是数据的个数),因为C+...+中最小的数据类型是 char,占一个字节的空间,而一个字节中有8个比特位,可以标识8个元素,所以在构造函数中我们将 vector resize 到 N/8+1 即可,这里加1是因为 C++ 中的除法是整数除法...---- 三、bitset C++ 中其实也提供了类似于位图这样的东西,只是 C++ 把它叫做位的集合 – bitset,它的功能比我们自己模拟实现的要更加丰富,不过主要功能比如 set、reset 和...我们发现,使用传统的位图并不能解决这个问题,因为位图只能表示在或不在,并不能表示某个数出现了几次;而位图只能表示在或不在是因为位图中一个数据只用一个比特位表示,而一个比特位只能标识两种状态,那么我们可以将两个位图合在一起...,然后遍历取出某一个位图中的数据与另一个位图进行 test。

    38010

    C#位图BitArray 小试牛刀

    前面聊了布隆过滤器,回归认识一下位图BitMap,阅读前文的同学应该发现了布隆过滤器本身就是基于位图,是位图的一种改进。...难缠的布隆过滤器,这次终于通透了 位图 先看一个问题, 假如有1千万个整数,整数范围在1到1亿之间,如何快速确定某个整数是否在这个1千万个整数中呢?...什么是位图?每一位存放某种状态,适用于海量数据,通常用于判断数据是否存在。位图的空间由数据的最大值决定。 位图这种数据结构来大大节省内存的使用量。...C# 有专业的位图数组:BitArray using System; using System.Collections; namespace Bitmap { class Program...myBA1 = myBA1.And(myBA2); return myBA1; } } } 最后提醒各位:宝藏组件Redis天然支持位图

    45930

    C++从小白到大牛】位图讲解

    引言: 我们首先通过一道腾讯的面试题来揭开位图的面纱~ 给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。【腾讯】 解题思路: 1....位图的概念: 所谓位图,就是用每一位(比特位)来存放某种状态,适用于海量数据,数据无重复的场景。通常是用来判断某个数据存不存在的。...思路二:使用位图 因为这里要表示多种状态,没有出现,出现1次,出现两次及以上,因此用1个比特位满足不了我们的需求,所以我们可以用两个比特位来解决! 同时我们可以利用两个位图来解决!...思路:分别set到两个位图,同时为1的就是交集 问题:那100亿个数,给1G的内存够用吗?...我们通过上一道题,可以知道给定100亿个数,需要两个大小为512M的内存作为位图,一共需要1个G,那这里一共就只有512MB,那该怎么办呢?

    7910

    C++】哈希(位图,布隆过滤器)

    今天的内容是哈希的应用:位图和布隆过滤器 ---- ---- 一、位图 1.位图概念 今天的内容从一道面试题开始引入: 给 40亿个不重复的无符号整数, 没排过序。...然后两个位图进行相与操作,同时为1说明是交集。 3....由前面所学,我们可能会想到位图,但是行不通,要统计次数就要开辟多个位图, 成倍的开辟位图来表示次数的话,会占用大量的内存空间,内存也存不下。...当然可以,可以使用哈希函数,将字符串转化为整型,再去映射到位图中。 当针对字符串来判断是否存在时,位图+哈希其实就是我们要讲的布隆过滤器。...那还有问题就是:一个字符串映射多个位图的位置,那位图应该开多大呢? 或者说如何选择哈希函数个数和布隆过滤器长度?

    30640

    C++位图】构建灵活的空间效率工具

    在本文中,我们将深入探讨如何在 C++ 中封装位图数据结构,重点介绍其基本操作、性能优化以及实际应用。通过封装,我们不仅可以提高代码的可读性和可维护性,还能为后续的功能扩展打下坚实的基础。...让我们一起来揭开位图的神秘面纱,探索其在现代编程中的价值。 位图 位图的基本概念 位图(Bitmap)是一种用于高效表示集合的数据结构,其核心思想是使用二进制位来指示某个元素是否存在。...如何用位图表示数据 我们是无法操作比特位的,C++操作内存的最小单位是字节,所以我们只能通过位运算来控制比特位,所以我们用 int类型的vector来控制。...size_t x) { size_t i = x / 32, j = x % 32; //取到j位置的值 return _bs[i] & (1 << j); } private: //C/...C++中定义的最小单位是一个字节 //一个int是32个位 std::vector _bs; }; 总结 在本文中,我们深入探讨了位图数据结构的基本概念及其在 C++ 中的封装实现。

    9810

    C++】位图应用 | 布隆过滤器

    位图应用 题目一 给40亿个不重复的无符号整数,没排过序,给一个无符号整数,如何快速判断一个数是否在这40亿个数中 ---- 正常思路: 1.排序 + 二分查找 2.放入 哈希表 或者 红黑树 ----...最少用一个char来表示一个值在不在 ,这样即为40亿字节即4GB,但是这样还是太大 标识在不在,并不需要将值存起来,使用0/1去表示 ---- 将每一个整数 所代表的值 用一个比特位去标识 即 位图...通过判断 两个比特位 是 1 /0 若出现次数为0,则 +1 变为 0 1 若出现次数为1 , 则+1 变为 1 0 若出现次数为1次以上,则不变 最终通过类中的print函数打印出出现一次的数 位图优缺点总结...布隆过滤器 提出背景 用哈希表存储 缺点:浪费空间 用位图存储 缺点: 位图一般只能处理整形,若为字符串,则无法处理 将哈希与位图结合 即布隆过滤器 概念 用多个哈希函数,将一个数据映射到位图结构中...通过调用对应hash1 hash2 hash3中的operator() 的不同实现 将传入对应的字符串转换为不同的整形,在使用位图插入在不同的映射位置 ---- tset 只有当hash1 hash2

    18720

    C++修炼之路】24.哈希应用--位图

    哈希应用--位图 一.提出问题 二.位图概念 三.位图代码 四.位图应用 五.经典问题 一.提出问题 问题: 给40亿个不重复的无符号整数,没排过序。...毫无疑问,位图很容易解决 将每个文件种的数都用位图标记,取位图的交集就可以找到文件的交集。...实际上使用位图就是为了去重,如果直接将一个文件的一部分去遍历另一个文件,虽然可以确定,但是难免一个文件中不会出现重复数据,所以使用位图。 三....以位图的方式就可以减少空间的占用。...位图同样不适用,因为找到出现次数最多的ip地址属于的问题,而位图的功能是找在或者不在的问题,以及出现的次数是确定的问题,属于,所以与位图无关。

    25200

    C++:位图和布隆过滤器

    1.1 位图的概念 究竟什么是位图呢??我们用一道问题来引入 问题:给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在 这40亿个数中。...1.2 位图的实现 首先,我们的STL容器中是有位图这个容器的,名字叫做bitset。...附上一道位图有关的OJ题 面试题 01.01....但是我们如果直接用一个为位图来解决,那么计算逻辑也会随之改变。所以我们还是用之前的位图,但是为了表示多种状态,我们使用两个位图。 00表示无,01表示1次,11表示2次,10表示2次以上即可。...用位图存储用户记录,缺点:位图一般只能处理整形,如果内容编号是字符串,就无法处理 了。 3.

    9310

    C++语法中bitset位图介绍及模拟实现

    一、位图的引入 先来看下边一道面试题: 给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。...O(N),而查找时时间复杂度为O(1),但是都有一个问题就是要将空间不足,40亿个无符号整形,需要160亿字节的空间,大概就是16GB的空间,一般计算机的内促都是4G或者8G,所以空间不足,此时就有了位图的方法来解决...二、位图的概念 所谓位图,就是用每一位来存放某种状态,适用于海量数据,数据无重复的场景。通常是用来判断某个数据存不存在的。 那么位图还有哪些应用呢?...快速查找某个数据是否在一个集合中 排序 + 去重 求两个集合的交集、并集等 操作系统中磁盘块标记 位图模拟实现 一、构造函数 由于不能按位开空间,所以我们选择每次开一个字节的空间,...所以 直接在构造函数中开好空间: bitset() { _bits.resize(N / 8 + 1,0); } 二、set,reset,test函数 set函数的作用是对位图中的某一位进行填充

    24430

    C语言】初识C语言(常见的C语言概念)

    一.C语言是什么?...语言大致可以分为自然语言和计算机语言,自然语言就是人与人日常交流的语言,如汉语、英语、日语等等,计算机语言又可以分为机器语言、汇编语言、高级语言C语言就是一个高级语言 机器语言:就是由二进制01组合起来的计算机可以直接识别的程序语言是一种面向机器的语言...,比起低级语言易懂易学,可移植性好,编程效率高,但是执行效率没有低级语言高,需要经过编译或解释,C语言就是采用编译的一种高级语言 二.为什么选择C语言 C语言常年霸榜各类高级语言前三,属于基础必学的语言...,其功能强大,而且许多语言都很相似,如果学好C语言,对学习其他语言也有很大帮助 三.编译器的选择 C语言是一门编译型的语言,需要依赖编译器将计算机语言转换成机器能够执行的机器指令 常见的编译器有:msvc...+文件,这里没有C文件选项,因为C++和C基本不分家,将后缀名.cpp改为.c就可以了,创建好后就可以开始写我们的第一个C语言程序了 注意:其中.c的文件叫源文件,.h的文件叫头文件(head),后面会慢慢讲到

    9610

    C++】C 语言C++ 语言的关系 ( C 语言发展 | C 语言缺陷 | C 语言 + 面向对象 + 高级语言特性 | C++ 语言增加内容 | C 语言C++ 语言应用场景 )

    一、C 语言发展 C 语言 被开发之前 并 没有经过 缜密 的 设计 , 而是在 使用过程中 逐渐完善的 ; C 语言发展经过如下阶段 : 初始阶段 : 1972年至1978年 , C语言 初步形成 ,...C99 , C11 , C17 等标准 , 以满足新的编程需求 ; 二、C 语言缺陷 C 语言有如下缺陷 : C 语言 没有经历过 缜密的 设计过程 , 都是根据需求逐渐完善的 , 出现了很多缺陷和漏洞...2、C 语言C++ 语言关系 C 语言C++ 语言 并 不是 竞争关系 ; C++ 语言 是 以 C 语言为基础 的 加强版本编程语言 , 可以看作是更好的 C 语言 , 在 C++ 语言...中 , 可以使用 C 语言语法 , 对 C 语言完全兼容 ; C++ 语言 包含 C 语言 , 在 C++ 代码中可以使用 C 语言的语法 , 但是在 C 语言中不能使用 C++ 的语法 ; 3、C++...语言应用场景 C 语言C++ 语言的应用场景 : C语言 应用场景 : 系统软件、操作系统、编译器等 底层系统级应用 ; C++ 语言 应用场景 : 大型应用程序、游戏 等更 高级的应用 ; 在不同的

    27820
    领券