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

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)
blank

相关推荐

  • UFT12.02 LICENSE延期

    UFT12.02 LICENSE延期1.以win7系统为例,安装完成后,修改图片目录下红色目录,仅第一次需修改2.删除红色目录,每次延期都需删除或修改此目录3.运行instdemo.exe,无报错,应该就延期成功了

  • 电子元器件品牌排行榜前十名

    电子元器件品牌排行榜前十名ameya360电子元器件采购网汇总了一些常见电子元器件常用品牌,大家在元器件选型时可以参考。电阻:Yageo国巨、Uniohm厚声、Walsin华新科、Fenghua风华、Ralec旺诠、KOA兴亚、Panasonic松下、AVX、Rohm罗姆、Samsung三星、TDK、TMTEC泰铭、Kyocera京瓷、PHYCOM飞元。电容:Yageo国巨、Samsung三星、Eyang宇阳、Murata村田、Taiyo太诱、Fenghua风华、Kyocera京瓷、HEC禾伸堂、Kemet基美、IS

  • 解决Pycharm和pip都安装TensorFlow失败的问题(Windows 10)

    解决Pycharm和pip都安装TensorFlow失败的问题(Windows 10)pip报错:Couldnotfindaversionthatsatisfiestherequirementtensorflow(fromversions:)NomatchingdistributionfoundfortensorflowPycharm报错:Erroroccuredwheninstallingpackage‘tensorflow’解决…

  • c语言length函数,length_length什么意思[通俗易懂]

    c语言length函数,length_length什么意思[通俗易懂]length什么意思length[英][leŋθ][美][lɛŋkθ,lɛŋθ]n.长度,长;时间的长短;(语)音长;一段,一节复数:lengths1.Abookisnotjudgedonlyonitslength.不能只根据篇幅长短来评价一本书。2.Ahallranthelengthoftheupperfloorofthehouse.走廊的长度等于房子…

  • n皇后问题 回溯法java_Java解决N皇后问题

    n皇后问题 回溯法java_Java解决N皇后问题问题描述:   要求在一个n×n的棋盘上放置n个皇后,使得它们彼此不受攻击。   按照国际象棋的规则,一个皇后可以攻击与之同一行或同一列或同一斜线上的任何棋子。   因此,n皇后问题等价于:要求在一个n×n的棋盘上放置n个皇后,使得任意两个皇后不在同一行或同一列或同一斜线上。一个皇后的攻击范围:                                    n皇后的解空间—完全n叉树…

  • 车载逆变器设计[通俗易懂]

    车载逆变器设计[通俗易懂]逆变器,别称为变流器、反流器,是一种可将直流电转换为交流电的器件,由逆变桥、逻辑控制、滤波电路三大部分组成,主要包括输入接口、电压启动回路、MOS开关管、PWM控制器、直流变换回路、反馈回路、LC振荡及输出回路、负载等部分,可分为半桥逆变器、全桥逆变器等。目前已广泛适用于空调、家庭影院、电脑、电视、抽油烟机、风扇、照明、录像机等设备中  逆变变压器原理  它的工作原理流

发表回复

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

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