生成不重复随机数
今天碰到一个生成不重复随机数题目, 题目类似如下:
在一个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之间的……