? ? ? ? “许多天以后，面对学校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 可代表的数据范围是：
????????????????????????????????????????????????????????????????????????????????????
如book[5]可表示的范围是33~40；book[60]可表示的范围是 473~480;book[125000]可表示的范围是999993~1000000。
而判断一个数字temp应该被存放到哪里，只需要根据以上公式推导出，应被存放在该下标指向的数组空间中：
??????????????????????????????????????????????????????????????????????????????????????????????????
如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]做或运算即可。这样我们就得到一个公式：
?????????????????????????????????????????????????????
看起来很麻烦对不对，但我们可以用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的题出的很好，下次不要再出了！