(算法)位图BitMap
算法 bitmap 位图
2023-09-14 08:59:06 时间
题目:
给定一数组,大小为M,数组中的数字范围为1-N,如果某带宽有限,无法传输该大小的数组,该怎么办?
思路:
通过位图BitMap来压缩数组,将数组中每个数字在bit位上标志,这样就可以将数组大小压缩很多倍,每个32位int只需要1bit来表示。
代码:
#include<iostream> #include<string.h> using namespace std; char* compression(int *A,int imax,int n){ int m=(imax-1)/8+1; //int bits[m]={0}; char *bits=new char(m); memset(bits,0,m*sizeof(int)); int byte_offset; int bit_offset; for(int i=0;i<n;i++){ byte_offset=(A[i]-1)/8; bit_offset=7-(A[i]-1)%8; bits[byte_offset] |=1<<bit_offset; } for(int i=0;i<m;i++) cout<<int(bits[i])<<" "; cout<<endl; return bits; } void* depression(char *B,int m){ //int n=m*8; //int *A=new int(n); for(int i=0;i<m;i++){ for(int j=7;j>=0;j--){ if((B[i]>>j)&1) cout<<i*8+8-j<<" "; } } cout<<endl; } int main(){ int A[]={1,3,7,9,4,6,8,10,16,20}; int n=sizeof(A)/sizeof(A[0]); int imax=0; for(int i=0;i<n;i++){ if(A[i]>imax) imax=A[i]; } char *B; B=compression(A,imax,n); int m=(n-1)/8+1; depression(B,m); return 0; }
相关文章
- Java实现 蓝桥杯 算法训练 Multithreading
- Java实现 蓝桥杯VIP 算法提高 密码锁
- Java实现 蓝桥杯VIP 算法提高 士兵排队问题
- Java实现 蓝桥杯VIP 算法提高 盾神与砝码称重
- Java实现 蓝桥杯VIP 算法训练 Hankson的趣味题
- Java实现 蓝桥杯VIP 算法训练 麦森数
- (算法)前K大的和
- 数据结构和算法学习六,之非递归排序
- 简单易学的机器学习算法—SVD奇异值分解
- (算法)位图BitMap
- (算法)最长重叠线段或区间
- 【YOLOv8/YOLOv7/YOLOv5/YOLOv4/Faster-rcnn系列算法改进NO.60】损失函数改进为wiou
- 数学建模学习(84):鲸鱼优化算法(WOA)对多元函数寻优
- m基于遗传优化算法的车辆货物运输问题matlab仿真,包括行驶距离,等待卸货时间及货损等问题
- Python实现GWO智能灰狼优化算法优化Catboost分类模型(CatBoostClassifier算法)项目实战
- 【Python算法】实验5-计算中值及分治技术
- 数据结构与算法之快速排序
- (4)YOLOV5算法二之数据集转换及自动划分、随机划分训练集与测试集
- C/C++语言使用技巧(三十三):强大的数学计算库gsl与算法实现