题解 | 明明的随机数
明明的随机数
https://www.nowcoder.com/practice/3245215fffb84b7b81285493eae92ff0
#include <stdio.h>
#include <stdlib.h>
int main()
{
int n,a;
while(scanf("%d",&n) != EOF)
{
unsigned char bitmask[125] = {0};
for(int i=0;i<n;i++)
{
scanf("%d",&a);
bitmask[(a-1)/8] |= (1 << ((a-1)%8)); //如5，bitmask[0]:00010000;不减1就要申请126个字节的空间l;
}
for(int i=1;i<=1000;i++)
{
if(bitmask[(i-1)/8] & (1 << (i-1)%8)) //查询1到1000对应的位是否被置1;
{
printf("%d\n",i);
}
}
}
return 0;
}
基于桶排序的位运算，桶排序需要分配int count[1000]的大小，来记录题目给定范围的整数a(1~1000)有没有出现过，出现就count[a]置1，然后i从最小值1开始遍历到1000，并用if(count[i])判断，成立则输出i；
位运算改进，申请unsigned char bitmask[1000/8]的大小，以bit来标记是否数字出现，如1，就在bitmask[0]的bit0，二进制表现为00000001；8就是第0个字节的bit7，二进制为10000000；1000，就在bitmask[124]的bit7。
