欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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;
}
相关标签: 骑牛学习笔记