【必看】【bitmap算法】只使用C语言的基本知识,该如何用很小的内存对大量数字去重排序?(哈理工OJ2505)

        “许多天以后,面对学校OJ上刺眼的“Latest Unsolved”的时候,我一定会想起进入大学后第一次月赛的那个遥远的下午。当时,我是个只会桶排的freshman。”当我面对学校组织的月赛中“非常简单的去重排序”一题,丝毫没有顾及900K的内存限制,对着10^6的数据冲了近二十发……这墙裂打击了我这脆弱的心灵。面对着满屏的MLE,我只想向世界呐喊:“淦!

        不过我们打码人怎么能轻易倒下 w(゚Д゚)w!!!当时的我不能说是发奋图强吧,至少也算是心灰意冷了 ┑( ̄Д  ̄)┍(摆烂了,就是不会了,谁也别说了)。这两个多月里,在OJ上开心的刷着难度两三星的A+B问题们时,这个刺眼的Latest Unsolved始终是我的意难平。我终于是鼓起了和钱包一样瘪的勇气,再次打开了这道题。但这次,上帝以5G的速度向我脑海中传输了一个灵感!

1.桶排到底行不行?

        900K的内存,处理10^6次方的数据,如果直接开一个一百万大小的数组,下标即为数字,用0和1来标记数组值。每出现一个数字,则判断对应下标的数组值是否为0,若为0则标记为1。最后再遍历数组输出结果。但即使是开char数组,仅数组大小就达到了一百万字节,即为976K。这真是大象进了蜗牛壳——住不下啊。但是我们仔细一想,一个数组值只用来表示其下标数字是否存在,不是0就是1,那么,可不可以用一个char的数组空间来表示两个值呢?

        于是我想到,也许可以开一个50w大小的数组:该数组元素的下标值存在,就为该元素+1;该数组元素的下标值+50w的值存在,就为该元素+10(当然,在+1或+10前要判断该值是否是“加过1的”或是“加过10”的)。例如:

#include<stdio.h>

#define N 500000

char book[500005]={0};

int main()
{
    int t=0;
    scanf("%d",&t);//下面将输入t个数据
    for(;t>=1;t--)
    {
        int temp=0;
        scanf("%d",&temp);
        if(temp<=N)//小于五十万,考虑做+1标记
        {
            if(book[temp]%10==0)//除以十余数为零,这说明book[temp]尚未标记值temp
            {
                book[temp]++;
            }
        }
        else//接收到一个大于五十万的数字,考虑做+10标记
        {
            temp-=N;
            if(book[temp]/10==0)//除以十除数为零,这说明book[temp]尚未标记值temp+500000
            {
                book[temp]+=10;
            }
        }
    }
    for(int i=1;i<=N;i++)//遍历数组,输出从1到50w中哪些数字被标记
    {
        if(book[i]%10==1)
        {
            printf("%d ",i);
        }
    }
    for(int i=1;i<=N;i++)//遍历数组,输出从50w+1到100w中哪些数字被标记
    {
        if(book[i]/10==1)
        {
            printf("%d ",i+N);
        }
    }
    return 0;
}

        在原题中,要求行末不输出空格。以我的水平写出的不要求空格的版本略长。不过这里难度不大,可以用变量flag标记,也可以goto(goto大法好啊),所以就不放出来丢人了。当我把自以为正确的代码交上去的时候:

                                                         。。好吧,早就有预料。。

        不过这并不能消减我的信心:char的范围是-128~127,我还可以用100来标记,将100w的数据范围三等分(请原谅我用“等分”这个词,我们都知道,100w%3!=0)。我觉得,这方法,行!

2.多少个桶?

        100也可以用来标记,这让我陷入了深深的思考当中:-128~127的范围中,如此多的数字可以用来标记,那么。。

                                                        我为毛偏要选10的N次方啊??!!

        在unsigned char中,数据范围是0~255,其中0作为标记“无任何数字”值。那么,在剩下的255个数字中,我最多可以利用多少数字进行标记,而不会出现混乱呢?

        要找到这些满足要求的“标记数”,首先要回顾我们使用的解决问题的方法:我们把数组下标指向的数组元素分为“十位”和“个位”分别储存数据x和x+50w,也就是说,我们利用十进制数的每一位的数字大小来标记某个数的出现与否。十进制数对于char,只有三位数可用。那么。。。。

                                                                二进制,yyds!

         char可以表示256个数字,刚好8个二进制位(或者说,正因为char由8个二进制位组成,所以可以表示256个数字)。10的N次方苦弱!2的N次方飞升!!用0代表无记录,1,2,4,8,16,32,64,128各代表一个值,也就是说,一个char可以用来记录8个数字的出现情况!

 

        如果看到这里你还没明白,不妨看一下这个例子:

        假如我们此时需要对数列 5 7 6 5 7 5进行去重排序,这个序列中出现的所有数字都在1-8的范围呢。所以我们能用一个char的空间储存他们。首先是5:

 

                 在判断“5”这一位为0后,我们就需要标记这个数字的出现。而将“5”这一位标记,即为x(该数组元素值)|=1<<4。将1(0000 0001)左移(5-1)位后,就可以得到16(0001 0000)。x|=16,x就从0(0000 0000)变为了16(0001 0000)。接下来判断下一个数字7:

                当“7”这一位为0,且我们读取到“7”这个值时,我们就要改变该变量(数组元素)的值,以此来记录“7”的出现。标记第七位,即为x|=1<<6。将1(0000 0001)左移(7-1)位后,就可以得到64(0100 0000)。x|=64,x就从之前的(0001 0000)【仅标记了“5”的出现】变为了 (0101 0000)【标记了“5”和“7”的出现】。 

        我们用“temp”代表我们需要处理的数字,“x”代表用来储存数字当前存在状态的变量值。通俗的来说,就是

                                                             x|=(temp-1)%8

        但是这样只能记录1~8的存在状态,如何记录更多数据呢?

                                                                还得开数组

        但这次,我们不需要100w!也不要50w!!更不要33w!!!内存甩货!!OJ吐血大降价!!只要12.5w!只要12.5w!!12.5w,将100w个数字的存在状态带回家!!o(*≧▽≦)ツ

3.桶的数量确定了,怎么装呢

        12.5w长度的unsigned char数组,每个可以存放八个连续数字的存放状态。book[1]存放1~8;book[2]存放9~16;book[3]存放17~24……我们可以整理出 数组下标对应的数组元素值 与其 可代表的 八个连续的数字的 存放状态 的关系。简单来说,就是一个下标对应八个数字。上句话可能有点长,不过我相信你多读几遍时可以理解的(≖ ‿ ≖)✧

即下标 i 可代表的数据范围是:

                        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        (i-1)*8+1sim i*8

如book[5]可表示的范围是33~40;book[60]可表示的范围是 473~480;book[125000]可表示的范围是999993~1000000。

而判断一个数字temp应该被存放到哪里,只需要根据以上公式推导出,应被存放在该下标指向的数组空间中:

        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        (temp-1)/8+1

如5被存放在book[1];60被存放在book[8];125000被存放在book[15625]。

而temp的存储形式,也就是要将temp储存在book[(temp-1)/8+1]中的哪一位上,则根据temp对8的余数判断。余1,代表存放在第一位;余2,存放在第二位……余0则存放在第八位。存放在第一位,只需要加上0000 0001,而存放在第二位,就加上0000 0010……而第八位则是1000 0000。对于每一个temp,我们只需要令其-1,然后计算出其-1后的余数b,再将1左移b位。得到的数字去和book[a]做运算即可。这样我们就得到一个公式:

        ​​​​​​​        ​​​​​​​        ​​​​​​​        book[(temp-1)/8+1]|=(1<<((temp-1)%8)){color{Red} }

看起来很麻烦对不对,但我们可以用a,b两个变量来替换其中的公式。现在让我们来看一下代码吧:

#define N 125000

unsigned char book[N+1]={0};//用于存放数据的book数组

int n=0;//一共有n个数据
int temp=0;//temp作为临时变量,接收数据
scanf("%d",&n);
for(;n>=1;n--)
{
    scanf("%d",&temp);
    int a=(temp-1)/8+1;//a为下标
    int b=(temp-1)%8;//b决定temp的存储位
    book[a]|=(1<<b);//存储操作
}

怎么样,这样看起来舒服多了吧

4.装是装好了,那么怎么输出呢?

        现在距离成功只差一步:输出我们储存好的答案。看到这里,我想答案的输出方式已经呼之欲出了:遍历数组。我们设置两个变量:i用于遍历数组元素;j用于遍历每一个数组元素的八个二进制位,通过判断“是否为1”,达到判断某数字是否存在的效果。

int i=1;//i用于遍历数组
int j=8*(i-1)+1;//j用来遍历数组中的八个位

其中i从1~125000,j从8*(i-1)+1~8*i(如果对这里不太清楚,可以看一下前面的公式,对,就是下标i可代表的数据范围)

for(i=1;i<=125000;i++)//遍历数组
{
    j=8*(i-1)+1;//初始化j
    while(j<=8*i)//遍历八个位
    {
        if(book[i]%2==1)//如果最低的一位是1,就说明这个数字存在
        {
            printf("%d ",j);
        }
        j++;
        book[i]>>=1;//将book[i]右移一位,准备判断下一个位
    }
}

至此,用900K的数据解决100w个数字的去重排序问题就解决啦并没有解决,因为这道题还要求行末无多余空格。

无行末多余空格AC代码如下:

#include<stdio.h>

#define N 125000

unsigned char book[N+1]={0};//用于存放数据的book数组

int main()
{
    int n=0;//一共有n个数据
    int temp=0;//temp作为临时变量,接收数据
    scanf("%d",&n);
    for(;n>=1;n--)
    {
        scanf("%d",&temp);
        int a=(temp-1)/8+1;//a为下标
        int b=(temp-1)%8;//b决定temp的存储位
        book[a]|=(1<<b);//存储操作
    }
    int i=1;//i用于遍历数组
    int j=1;//j用来遍历数组中的八个位

    for(;i<=N;i++)//遍历数组
    {
        j=8*(i-1)+1;//初始化j
        while(j<=8*i)//遍历八个位
        {
            int flag=0;//用于记录第一个数字是否出现,如果出现,则跳出循环,再接下来的输出中输出空格
            if(book[i]%2==1)//如果最低的一位是1,就说明这个数字存在
            {
                printf("%d",j);
                flag=1;//记录下,已经有数字输出了
            }
            j++;
            book[i]>>=1;//将book[i]右移一位,准备判断下一个位
            if(flag==1)
            {
                goto A;//开始输出带空格的数据
            }
        }
    }
    for(;i<=N;i++)
    {
        j=8*(i-1)+1;//初始化j
        A:;while(j<=8*i)//这里标签A要在初始化j的下面,为了保证j的值不会因为goto而改变,导致漏掉数据
        {
            if(book[i]%2==1)
            {
                printf(" %d",j);
            }
            j++;
            book[i]>>=1;
        }
    }
    return 0;
}

 

                                        终于!结束了!!!

5.优化,猜想与总结

        当然,上面的代码还有很多可以优化的地方:比如使用flag变量和goto语句,以这样的方式来在数据间输出空格,是否会消耗较多的时间空间?变量a,b可以删去等等细节。实不相瞒,昨晚我第一次AC这段代码的时候,并未使用到位运算。最开始我想的是,1,2,4,8……128这个序列的任意不同的子序列的和都是唯一的,于是想到用1~128等数作为标记符,标记数字是否出现。每出现一个数字,如63,那么它就在book[8]中,对应的值为64(2的(8-2)次方)。而输出数据时,再对每一个数组元素值进行判定:从是否大于等于128开始,如果大于等于128,则减去128,输出8*i;然后判断是否大于等于64……但这样会导致时间复杂度较高,而且,这是降序排序。。。于是我换了个思路,是否可以用别的形式输出数据?我猛然发现:对于所有数据,其在二进制位中只占一个“1”,而其他的位都是“0”!因为他们都是2^N。于是我改变思路,开始考虑对每一个book数组值进行除以二的处理,低位为1,则代表有;否则就无。

        但是提交第一次AC的代码时,我仍然用的是“判断该数据转化成2^N形式后的数据是否储存在空间内,如果未储存,则储存”这样的比较笨的办法

scanf("%d",&temp);
if((book[(temp-1)/8+1]>>((temp-1)%8))%2==0)//不存在
{
    book[(temp-1)/8+1]+=(1<<((temp-1)%8));
}

但当我开始写这篇文章的时候,随着自己一点一点剖析自己的思路,我渐渐发现了很多逻辑误区和可以改进的地方,于是将这里直接改为“不判断,进行或操作”

scanf("%d",&temp);
int a=(temp-1)/8+1;//a为下标
int b=(temp-1)%8;//b决定temp的存储位
book[a]|=(1<<b);//存储操作

/*或操作:0|0=0;0|1=1;1|0=1;1|1=1*/

或操作可以让已经有的不被抹除,而没有的将被写上。这无疑大大减小了时间复杂度。

然鹅。。正当我沉浸在自己的惊人发现中沾沾自喜时,隐隐想到:

                        不会有人和我想得一样吧w(゚Д゚)w

。。然后,万能的互联网按照我的描述,让我认识了一个算法:Bitmap算法

于是,我在悲喜交加的情绪状态下写了这篇文章。喜就喜在,我和大佬想到一块去了。悲就悲在,已经2022年了。。。

 (PS:不过我还想到也许八个位可以不止表达八种状态:也许可以借鉴浮点数的储存状态,如果数据量大且连续性强,也许可以从八个位中抽出几位,用于表示下一段连续空间是否全充满/半充满,这样可以进一步压缩空间。不过由于本人能力不足,暂时想不到什么好办法,也不知道bitmap算法是否已经有这样的操作了,还望大佬在评论区可以解答,多谢多谢)

        至此,曾经困扰过我很久的问题终于被我找到了答案。无论是在猜想方案,构思,还是在上手写代码,调试逻辑bug,或是最后总结思路,写这篇文章,我都学到了很多东西,一次又一次的优化自己的想法,并把看似困难的问题一步一步简单化,最后也能用自己的语言来阐述自己的构思。

        总而言之:OJ的题出的很好,下次不要再出了!

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>