当前位置:首页 » 《关于电脑》 » 正文

【C++】位图

17 人参与  2024年05月07日 17:13  分类 : 《关于电脑》  评论

点击全文阅读


文章目录

1. 位图概念2. 位图的实现3. 位图的应用
在这里插入图片描述

1. 位图概念

面试题

给 40 亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这 40 亿个数中。

遍历,时间复杂度 O(N)

排序 O(NlogN),利用二分查找:logN

位图解决:

数据是否在给定的整型数据中,结果是在或者不在,刚好是两种状态,那么可以使用一个二进制比特位来代表数据是否存在,如果二进制比特位为 1,代表存在,为 0 代表不存在。

在这里插入图片描述

位图概念

所谓位图,就是用每一位来存放某种状态,适用于海量数据,数据无重复的场景。通常是用来判断某个数据存不存在的。

2. 位图的实现

template<size_t N>class bitset{public:bitset(){_bits.resize(N / 32 + 1, 0);}// 把 x 映射的位标记成 1void set(size_t x){assert(x <= N);size_t i = x / 32;size_t j = x % 32;_bits[i] |= (1 << j);}// 将 x 映射的位标记成 0void reset(size_t x){assert(x <= N);size_t i = x / 32;size_t j = x % 32;_bits[i] &= ~(1 << j);}// 检测位图中 x 是否为 1bool test(size_t x){assert(x <= N);size_t i = x / 32;size_t j = x % 32;return _bits[i] & (1 << j);}private:vector<int> _bits;};

3. 位图的应用

快速查找某个数据是否在一个集合中;排序 + 去重;求两个集合的交集、并集等;操作系统中磁盘块标记;…
END

点击全文阅读


本文链接:http://m.zhangshiyu.com/post/104770.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • [完结]沈淮安陆心玥(又名:暗恋青梅十年我选择放手)新上全
  • 暴雨惊魂夜:+后续(陆舟吴佳)全书免费_(陆舟吴佳)暴雨惊魂夜:+后续后续(陆舟吴佳)
  • 我死遁后,族长悔疯了:结局+番外(我死遁后,族长悔疯了:结局+番外)_我死遁后,族长悔疯了:结局+番外(战痕音音)列表_笔趣阁(战痕音音)
  • 温长生陆扶摇(温长生陆扶摇:结局+番外)完结_温长生陆扶摇列表_笔趣阁(温长生陆扶摇:结局+番外)
  • 梁岁霍司年叶琳完本(又名:似月光吻野风)完本_完本梁岁霍司年叶琳完本(又名:似月光吻野风)
  • 全书免费周宴礼宋知蔓(又名:改嫁闲散王爷后负心将军跪求我原谅)_周宴礼宋知蔓(又名:改嫁闲散王爷后负心将军跪求我原谅)全书免费
  • 天鹅曾坠落(江舒白秦蓁)_天鹅曾坠落(江舒白秦蓁)
  • [爱的莫比乌斯环]精彩节选免费试读_江子安娇娇老公节选免费试读
  • 温长生陆扶摇:结局+完结宝藏_温长生陆扶摇:结局+完结宝藏
  • 好看的温长生陆扶摇:结局+完结宝藏_温长生陆扶摇:结局+完结宝藏
  • 全书免费娘子为师弟夺我秘宝后我灭她满门月婵柳安澜李凤年在线(又名:娘子为师弟夺我秘宝后我灭她满门)_娘子为师弟夺我秘宝后我灭她满门月婵柳安澜李凤年在线(又名:娘子为师弟夺我秘宝后我灭她满门)全书免费
  • 离婚后嫁死对头,冷傲总裁红了眼:+后续列表_离婚后嫁死对头,冷傲总裁红了眼:+后续(姜岁宁顾寒川)

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1