数据结构面试题之位图查找

1.思路有的人一看到这个题,很简单嘛最麻烦的就是从头遍历一遍的事情嘛. 不过要看清楚题! 40亿个无符号整数.我们生活中1G内存占用的字节数1024*1024*1024为10

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

题目: 给40个亿不重复的无符号整数,没有排序过,随机给出一个无符号整数,快速的判断这个数在或者不在40亿个数中?

1. 思路 

  有的人一看到这个题,很简单嘛最麻烦的就是从头遍历一遍的事情嘛. 不过要看清楚题! 40亿个无符号整数.  我们生活中1G内存占用的字节数1024*1024*1024为1073741824个字节.粗略就是10亿个字节. 而40亿个无符号整数是160亿个字节. 也就是这些数据存储下来需要16G的内存. 那么问题来了,普通的工作电脑的内存都4G,好点的就是8G. (如果你是16G内存光速吃鸡那么当我没说)我们可以发现这些数据的内存大于电脑的内存所以存储不下. 这个时候就很头大了,内存都存不下那么你怎么读取呢? 当然你说你直接去硬盘里面读.好! 没问题.从硬盘里面读取数据的速度和从内存中读取的速度根本没得比的.如果你的时间多也可以.不过我们有一个更厉害的方法就是我们的位图.位图就是给定一段连续的空间然后让这个空间的每一位都为0,再然后让每一个位表示一个数字.再然后当你这个数字出现的 时候将它对应的那个位->置为1.这样的话存储40亿个数据,也就是存储40亿个位.也就是5亿个字节.大概512MB的样子. 这样的话我们的内存存储这些数据也就是绰绰有余了.所以位图对于大数据的问题有着显著的效果。

2. 代码实现

#include "stdio.h"

// 用位图的方式实现大数据的查找
#include <vector>
#include <iostream>
using namespace std;

class CBitmapFind
{
    enum{INFOBITS_IN_VECT = 8};
public:
    // 确定容器大小
    explicit CBitmapFind(size_t nRange = 0)
    {
        BitmapVect.resize(nRange / INFOBITS_IN_VECT + 1);
    }
    // 添加单个元素并标记该元素
    void AddElement(int nNum)
    {
        // 确定该数据所在vect中的位置
        int nVectIndex = nNum / INFOBITS_IN_VECT;
        // 确定在vect索引中的byte位置
        int nByteIndex = nNum % 8;
        
        BitmapVect[nVectIndex] |= (1 << nByteIndex);
    }
    // 删除单个元素并移除单个元素
    void MoveElement(int nNum)
    {
        // 确定该数据所在vect中的位置
        int nVectIndex = nNum / INFOBITS_IN_VECT;
        // 确定在vect索引中的byte位置
        int nByteIndex = nNum % 8;
        
        BitmapVect[nVectIndex] &= ~(1 << nByteIndex);
    }

    bool TestBit(int nNum)
    {
        // 确定该数据所在vect中的位置
        int nVectIndex = nNum / INFOBITS_IN_VECT;
        // 确定在vect索引中的byte位置
        int nByteIndex = nNum % 8;

        return (BitmapVect[nVectIndex] & (1 << nByteIndex)? true:false);
    }
private:
    vector<char> BitmapVect;
};

3. 扩展:判断出现是次数是否大于3

// 用位图的方式实现大数据的查找,判断出现的次数,下面的代码只能处理出现次数小于等于3的情况
// 00 01 10 11
class CNBitmapFind
{
public:
    enum{ INFOBITS_IN_VECT = 4 };
    // 确定容器大小
    explicit CNBitmapFind(size_t nRange = 0)
    {
        BitmapVect.resize(nRange / INFOBITS_IN_VECT + 1);
    }
    // 添加单个元素并标记该元素出现的次数
    void AddElement(int nNum)
    {
        // 确定该数据所在vect中的位置
        int nVectIndex = nNum / INFOBITS_IN_VECT;
        // 确定元素在vect索引中的byte位置
        int nByteIndex = nNum % INFOBITS_IN_VECT;
        nByteIndex *= 2;

        bool first = BitmapVect[nVectIndex] & (1 << nByteIndex);
        bool second = BitmapVect[nVectIndex] & (1 << (nByteIndex + 1));

        if (!(first && second))
        {
            BitmapVect[nVectIndex] += (1 << nByteIndex);
        }
    }

    int Test(int nNum)
    {
        // 确定该数据所在vect中的位置
        int nVectIndex = nNum / INFOBITS_IN_VECT;
        // 确定元素在vect索引中的byte位置
        int nByteIndex = nNum % INFOBITS_IN_VECT;

        nByteIndex *= 2;
        int first = BitmapVect[nVectIndex] & (1 << nByteIndex)?1:0;
        int second = BitmapVect[nVectIndex] & (1 << (nByteIndex + 1))?1:0;

        return second * 2 + first;
    }
private:
    vector<char> BitmapVect;
};

4. 测试

void main()
{
    int nReange = 4 * pow(10, 2);
    CBitmapFind BitmapFind(nReange);
    for (int i = 0; i < nReange; i++)
    {
        BitmapFind.AddElement(i);
    }
    cout << "CBitmapFind测试:" << endl;
    BitmapFind.TestBit(401) ? (cout << "找到:" << 401 << endl) : (cout << "未找到" << 401 << endl);
    BitmapFind.TestBit(388) ? (cout << "找到" << 388 << endl) : (cout << "未找到" << 388 << endl);

    CNBitmapFind NBitmapFind(6);
    NBitmapFind.AddElement(1);
    NBitmapFind.AddElement(1);
    NBitmapFind.AddElement(1);
    NBitmapFind.AddElement(2);
    NBitmapFind.AddElement(2);
    NBitmapFind.AddElement(3);

    cout << "CNBitmapFind测试:" << endl;
    cout << "1出现的次数:" << NBitmapFind.Test(1) << endl;
    cout << "2出现的次数:" << NBitmapFind.Test(2) << endl;
    cout << "3出现的次数:" << NBitmapFind.Test(3) << endl;
}

数据结构面试题之位图查找

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/120125.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • jdk下载与安装[通俗易懂]

    1.JDK下载地址:http://www.oracle.com/technetwork/java/javase/downloads/index.html安装完成后,需要进行环境变量的配置,右键我的电脑—属性—-高级系统设置就会看到下面的界面:2.点击环境变量,开始坏境变量的配置:(1)点击系统变量下的新建按钮,变量名JAVA_HOME(代表你的JDK安装路径),值对应的是你的JDK的安装路径。(2)继续在系统变量里面新建一个CLASSPATH变量,其变量值如下图所示:….

  • 《计算机网络》复习笔记

    《计算机网络》复习笔记《计算机网络》复习笔记本复习笔记基于谢希仁的《计算机网络》第五版教材整理。计算机网络复习笔记绪论1计算机网络2因特网概述3互联网的组成P84计算机网络的类别P175计算机网络的体系结构P25物理层1物理层下的传输媒体2关于信道的几个基本概念3信道复用技术数据链路层1使用点对点信道的数据链路层2点对点协议PPPP703

  • vue beforeEach 跳转问题

    vue beforeEach 跳转问题我们直接在beforeEach函数里面判断用户是否登录然后跳转页面的时候会陷入一个死循环解决办法就是多加一层if判断首先判断用户是否有token或者时候登录然后再判断to参数里的path路径if(Lkcommon.getToken()){next()}else{if(to.path!==”/login”){next({path:”/lo…

  • softmax、softmax损失函数;交叉熵、交叉熵损失函数

    softmax、softmax损失函数;交叉熵、交叉熵损失函数

  • oracle srvctl命令,Oracle SRVCTL使用说明

    oracle srvctl命令,Oracle SRVCTL使用说明SRVCTL是Oracle9iRAC集群配置管理的工具。本文是对SRVCTL的所有命令进行详细说明的一篇参考文档。添加数据库或实例的配置信息。在增加实例中,与-i一起指定的名字应该与INSTANCE_NAME和ORACLE_SID参数匹配。srvctladddatabase-ddatabase_name[-mdomain_name]-ooracle_home[-sspfi…

  • matlab plotyy 坐标轴设置,[转载]Matlab plotyy画双纵坐标图实例[通俗易懂]

    matlab plotyy 坐标轴设置,[转载]Matlab plotyy画双纵坐标图实例[通俗易懂]Matlabplotyy画双纵坐标图实例x=0:0.01:20;y1=200*exp(-0.05*x).*sin(x);y2=0.8*exp(-0.5*x).*sin(10*x);[AX,H1,H2]=plotyy(x,y1,x,y2,’plot’);set(AX(1),’XColor’,’k’,’YColor’,’b’);set(AX(2),’XColor’,’k’,’YCol…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号