【C++ 学习 ㉖】- 位图详解(哈希扩展)
目录
一、位图的概念
二、位图的实现
2.1 - bitset.h
2.2 - test.cpp
三、位图的应用
3.1 - 例题一
3.2 - 例题二
一、位图的概念
假设有这样一个需求:在 100 亿个整型数字中快速查询某个数是否存在其中,并假设是 32 位操作系统,4 GB 内存。
由于数字的数量如此之多,如果使用一个 int 型的数组进行存储,需要占用的内存空间为 ,那么如何用更小的空间来 "存储" 这些数字呢?
我们可以用比特位(bit)来标记数字,每个比特位中存放的值则表示其标记的数字是否存在,0 表示不存在,1 表示存在,这就是位图的基本思想。
例如,标记数字 1、2、4、6:

由于 int 总共有 种取值,所以标记所有这些数字需要占用的内存空间为
。
二、位图的实现
2.1 - bitset.h
#pragma once
#include <vector>
namespace yzz
{template<size_t N> // 总共有 N + 1 个比特位class bitset{public:bitset() : _v(N / 32 + 1) { }
void set(size_t x){size_t i = x / 32;size_t j = x % 32;_v[i] |= (1 << j);}
void reset(size_t x){size_t i = x / 32;size_t j = x % 32;_v[i] &= ~(1 << j);}
bool test(size_t x) const{size_t i = x / 32;size_t j = x % 32;return _v[i] & (1 << j);}private:std::vector<int> _v;};
}
2.2 - test.cpp
#include "bitset.h"
#include <iostream>
using namespace std;
int main()
{int arr[] = { -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5 };yzz::bitset<0xffffffff> bs;for (const int& e : arr){bs.set(e);}bs.reset(-3);bs.reset(3);for (const int& e : arr){if (bs.test(e))cout << e << " ";}// -5 -4 -2 -1 0 1 2 4 5cout << endl;return 0;
}
三、位图的应用
位图的应用是大量数据的快速排序、查找和去重。
3.1 - 例题一
给定 100 亿个整数,找到只出现一次的所有整数。
doublebitset.h:
#pragma once
#include "bitset.h"
namespace yzz
{template<size_t N>class doublebitset{public:void set(size_t x){if (_bs1.test(x) == 0 && _bs2.test(x) == 0) // 00 -> 01{_bs2.set(x);}else if (_bs1.test(x) == 0 && _bs2.test(x) == 1) // 01 -> 10{_bs1.set(x);_bs2.reset(x);}// 10 则不变}
bool isSingleNum(size_t x) const{return _bs1.test(x) == 0 && _bs2.test(x) == 1;}private:bitset<N> _bs1;bitset<N> _bs2;};
}
思路:用 2 个比特位来表示一个数字的状态,00 表示不存在,01 表示只出现一次,10 表示出现一次以上。
具体实现则是使用两个位图。
思考:给定 100 亿个整数,找到出现次数不超过 2 次的所有整数。
思路是类似的,用 2 个比特位来表示一个数字的状态,00 表示不存在,01 表示只出现一次,10 表示出现两次,11 表示出现两次以上。
test.cpp:
#include "doublebitset.h"
#include <iostream>
using namespace std;
int main()
{int arr[] = { -3, -3, -2, -1, -2, 0, 1, 1, 2, 2, 3 };yzz::doublebitset<0xffffffff> dbs;for (const int& e : arr){dbs.set(e);}for (const int& e : arr){if (dbs.isSingleNum(e))cout << e << " ";}// -1 0 3cout << endl;return 0;
}
3.2 - 例题二
给两个文件,分别有 100 亿个整数,求两个文件的交集。
法一:
#include "bitset.h"
#include <iostream>
using namespace std;
int main()
{int arr1[] = { -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5 };int arr2[] = { -3, -3, -2, -1, -2, 0, 1, 1, 2, 2, 3 };yzz::bitset<0xffffffff> bs1;yzz::bitset<0xffffffff> bs2;// 去重for (const int& e : arr1){bs1.set(e);}for (const int& e : arr2){bs2.set(e);}// 求交集for (int i = -10; i <= 10; ++i){if (bs1.test(i) && bs2.test(i))cout << i << " ";}// -3 -2 -1 0 1 2 3cout << endl;return 0;
}
法二:
#include "bitset.h"
#include <iostream>
using namespace std;
int main()
{int arr1[] = { -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5 };int arr2[] = { -3, -3, -2, -1, -2, 0, 1, 1, 2, 2, 3 };yzz::bitset<0xffffffff> bs;for (const int& e : arr1){bs.set(e);}for (const int& e : arr2){if (bs.test(e)){cout << e << " ";bs.reset(e); // 避免出现重复的数字}}// -3 -2 -1 0 1 2 3cout << endl;return 0;
}相关文章:
【C++ 学习 ㉖】- 位图详解(哈希扩展)
目录 一、位图的概念 二、位图的实现 2.1 - bitset.h 2.2 - test.cpp 三、位图的应用 3.1 - 例题一 3.2 - 例题二 一、位图的概念 假设有这样一个需求:在 100 亿个整型数字中快速查询某个数是否存在其中,并假设是 32 位操作系统,4 GB…...
天启科技联创郭志强:趟遍教育行业信数化沟坎,创业智能赛道重塑行业生态
郭志强 天启科技联合创始人 近20年互联网、企业信息化、数字化实施、管理及培训经验。对于集团型企业及初创企业、传统企业及互联网企业的信息化、数字化转型有自己独到的见解和实操经验。具备跨区域、集团化信息规划、解决方案、系统架构及企业流程搭建、优化和技术团队管理能…...
Cuckoo沙箱各Ubuntu版本安装及使用
1.沙箱简介 1.1 沙箱 沙箱是一个虚拟系统程序,允许你在沙箱环境中运行浏览器或其他程序,因此运行所产生的变化可以随后删除。它创造了一个类似沙盒的独立作业环境,在其内部运行的程序并不能对硬盘产生永久性的影响。 在网络安全中ÿ…...
什么是mvvm模式,优点是什么
MVVM(Model-View-ViewModel)模式是一种设计模式。它是一种开发模式,旨在分离用户界面的开发和业务逻辑的开发。MVVM模式将应用程序分为三个部分: Model:它代表应用程序的数据模型和业务逻辑。 View:它代表…...
C/C++ 中的函数返回局部变量以及局部变量的地址?
C/C中,函数内部的一切变量(函数内部局部变量,形参)都是在其被调用时才被分配内存单元。形参和函数内部的局部变量的生命期和作用域都是在函数内部(static变量的生命期除外)。子函数运行结束时,所有局部变量的内存单元会被系统释放。在C中&…...
springboot和vue:七、mybatis/mybatisplus多表查询+分页查询
mybatisplus实际上只对单表查询做了增强(速度会更快),从传统的手写sql语句,自己做映射,变为封装好的QueryWrapper。 本篇文章的内容是有两张表,分别是用户表和订单表,在不直接在数据库做表连接的…...
【Leetcode】 51. N 皇后
按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 研究的是如何将 n 个皇后放置在 nn 的棋盘上,并且使皇后彼此之间不能相互攻击。 给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。 每一种…...
Java数据库连接:JDBC介绍与简单示例
Java数据库连接:JDBC介绍与简单示例 在Java程序中,操作数据库是必不可少的。JDBC(Java Database Connectivity)是Java中用于连接和操作数据库的一种技术。通过JDBC,Java程序可以与各种关系型数据库进行交互࿰…...
智慧茶园:茶厂茶园监管可视化视频管理系统解决方案
一、方案背景 我国是茶叶生产大国,茶叶销量全世界第一。随着经济社会的发展和人民生活水平的提高,对健康、天然的茶叶产品的消费需求量也在逐步提高。茶叶的种植、生产和制作过程工序复杂,伴随着人力成本的上升,传统茶厂的运营及…...
springboot整合pi支付开发
pi支付流程图: 使用Pi SDK功能发起支付由 Pi SDK 自动调用的回调函数(让您的应用服务器知道它需要发出批准 API 请求)从您的应用程序服务器到 Pi 服务器的 API 请求以批准付款(让 Pi 服务器知道您知道此付款)Pi浏览器向…...
类 ChatGPT 模型存在的局限性
尽管类ChatGPT模型经过数月的迭代和完善,已经初步融入了部分领域以及人们的日常生活,但目前市面上的产品和相关技术仍然存在一些问题,以下列出一些局限性进行详细说明与成因分析: 1)互联网上高质量、大规模、经过清洗…...
Nginx的安全控制
安全控制 关于web服务器的安全是比较大的一个话题,里面所涉及的内容很多,Nginx反向代理是安全隔离来提升web服务器的安全,通过代理分开了客户端到应用程序服务器端的连接,实现了安全措施。在反向代理之前设置防火墙,…...
字符串与字符编码 - GO语言从入门到实战
字符串与字符编码 - GO语言从入门到实战 字符串 与其他主要编程语⾔的差异 基本数据类型:string 是基础数据类型,而不是引用类型或指针类型。string 在内存中占用的空间大小是固定的,且只读、不可改变。字节切片:string 是只读…...
12P4375X042-233C KJ2005X1-BA1 CE3007 EMERSON servo controller
12P4375X042-233C KJ2005X1-BA1 CE3007 EMERSON servo controller 我们提供三种不同类别的EDGEBoost I/O模块供选择,以实现最大程度的I/O定制: 数字和模拟输入/输出网络和连接边缘人工智能和存储 利用EDGEBoost I/O实现变革性技术 EBIO-2M2BK EBIO-2M2BK载板支持…...
WPF向Avalonia迁移(四、其他事项)
开发必备 1. Avalonia项目源代码!!!!!!!!!!没有源代码,你连控件的背景色怎么改都找不着!! 2.下载你所使用的版本&#x…...
Python 代码调试
from pdb import set_trace as stx 是一个Python代码中常用的调试技巧之一,它用于在代码中插入断点以进行调试。这行代码的作用是将Python标准库中的 pdb(Python Debugger)模块中的 set_trace 函数导入,并将其重命名为 stx&#x…...
DM宣传单制作,利用在线模板,快速替换文字
如果你需要制作一批宣传单,但是时间很紧,而且没有专业的设计人员协助,那么你可以选择使用在线模板来快速制作宣传单。本文将介绍如何使用乔拓云平台,快速制作宣传单的方法。 步骤一:选择适合的在线制作工具 首先&…...
【力扣】42. 接雨水
这道题我卡了差不多1个小时,不是不会做,是不知道怎么能用栈来实现,后面看了一个博主的视频,豁然开朗,我主要的纠结点在于当指针指到7的时候,我计算出4到7的水块是2,但实际上是0,因为…...
IPETRONIK数据采集设备携手Softing Q-Vision软件致力于ADAS测试方案
一 背景 汽车ADAS技术是当下国内外的重点研究方向,且ADAS的发展水平和市场竞争力紧密相关,因此一套完善的ADAS测试方案对各整车厂而言非常重要。然而,国内ADAS测试却面临着很多阻碍,主要原因在于:相关测试设备昂贵&am…...
Go语言中的指针介绍
Go语言中的指针 文章目录 Go语言中的指针一、Go语言中的指针介绍1.1 指针介绍1.2 基本语法1.3 声明和初始化1.4 Go 指针的3个重要概念1.4.1 指针地址(Pointer Address)1.4.2 指针类型(Pointer Type)1.4.3 指针取值(Poi…...
Xshell远程连接Kali(默认 | 私钥)Note版
前言:xshell远程连接,私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...
代理篇12|深入理解 Vite中的Proxy接口代理配置
在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...
在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案
这个问题我看其他博主也写了,要么要会员、要么写的乱七八糟。这里我整理一下,把问题说清楚并且给出代码,拿去用就行,照着葫芦画瓢。 问题 在继承QWebEngineView后,重写mousePressEvent或event函数无法捕获鼠标按下事…...
Java求职者面试指南:计算机基础与源码原理深度解析
Java求职者面试指南:计算机基础与源码原理深度解析 第一轮提问:基础概念问题 1. 请解释什么是进程和线程的区别? 面试官:进程是程序的一次执行过程,是系统进行资源分配和调度的基本单位;而线程是进程中的…...
Web中间件--tomcat学习
Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机,它可以执行Java字节码。Java虚拟机是Java平台的一部分,Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...
打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用
一、方案背景 在现代生产与生活场景中,如工厂高危作业区、医院手术室、公共场景等,人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式,存在效率低、覆盖面不足、判断主观性强等问题,难以满足对人员打手机行为精…...
