20201205 快速定位,位图巅峰算法,你值得拥有!
程序员文章站
2022-07-09 13:45:51
...
//位图算法
/*需求:有一个整型数组,最大的40亿,最小的0,要求快速找到数组中是否存在某个数值
实现:位图算法
在堆空间中申请一块最大值的连续空间,将数组中的数值装载进去,装载的方法是,此数存在,则将相应
的位置1。装载完毕后,检测输入的数据是否在连续空间对应的位是否为1,如为1就存在,否则不存在。
*/
#include <iostream>
#include <Windows.h>
void loadData(char* data,unsigned int num) {
char* p = NULL;
//装载数据,假设能够被3整除的数据被装载进去
for (unsigned int i = 0; i < num; i++) {
if (0 == i % 3) {
p = data + i / 8;//找到对应的字节数
*p = *p | (1 << (i % 8));//找到对应的位
}
}
}
bool checkData(char* data, int num) {
char* p = data + num / 8;
return (*p & (1 << (num % 8)));
}
int main() {
unsigned int num = 4000000000;
unsigned int len = num / 8 + 1;
char* data = new char[len];
memset(data, 0, len);
loadData(data,num);
while (1) {
printf_s("请输入一个整数[输入-1退出]:");
scanf_s("%d", &num);
if (-1 == num) {
break;
}
if (checkData(data,num)) {
printf_s("该数据在数组中存在\n");
}
else {
printf_s("该数据在数组中不存在\n");
}
}
delete []data;
system("pause");
return 0;
}
上一篇: python实现凯撒密码加解密
下一篇: python实现凯撒密码、凯撒加解密算法