今天碰到一个生成不重复随机数题目, 题目类似如下:
在一个1K的数组中生成1~1M之间的随机数, 1K中的随机数不能重复.
第一反应就是暴力查询, 每生成一次就去已有的数据查询, 时间复杂度为O(n2). 效率极差.
仔细思考后发现这样一种特性, 数值空间为1~1M, 需要取出1K个数据, 1M = 1K * 1K
类似下面代码:
int buff[1024];
int tmp = 0;
for (i = 0; i < 1024; i++) {
tmp += 1024;
buff[i] = tmp;
}
上面的代码如果执行完毕那么tmp的结果会成为1M.
将一个0~1023之间的随机值替换上面的1024, 将能保证tmp的值一定小于等于1M, 由于递增的特性也可保证每个循环tmp的值是在0~1M中的惟一值.更改后代码如下:
int buff[1024];
int tmp = 0;
for (i = 0; i < 1024; i++) {
tmp += srand() % 1024;
buff[i] = tmp;
}
从代码中可以看到tmp由上一次tmp的值和这一次的随机值决定. 因此生成的值一定是随机的.
虽然生成的数是随机的, 但是在数组中的布局却是从小到大来分布的, 因为我们在赋数组时同样需要随机分布. 修改代码如下:
int buff[1024];
int tmp = 0;
int buff_index = 0;
memset(buff, 0xff, sizeof(buff[0]) * 1024);
for (i = 0; i < 1024; i++) {
tmp += srand() % 1024;
buff_index += rand();
buff_index %= 1024;
while (buff[buff_index] != -1) {
buff_index++;
buff_index %= 1024;
}
buff[buff_index] = tmp;
}
在写入数组时采用随机生成索引号的方法来决定要写到数值的哪一个位置, 如果这个位置被写过, 那么顺序向下查找空间数组位置, 因为数组共有1024个, 因为不管怎么样每次总能找到一个没有被写过的数组位置, 这样写入1024次之后一定会生成内存分布随机的1024个不重复的随机数.
btw: 清风同学说这个算法有个bug, 就是我第一个随机数一定会生成0~1024之间的数, 暂时还没有想到办法.