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

【C++】位图

23 人参与  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