一道看似不起眼的小题

zhendehaoren

面试的时候最怕遇到“小题”

这次栽在了这样的一道题上面：
a[1000]数组， 用随机函数随机生成1000次填充，不允许重复，也就是说不止1000次，复杂度最低实现

以下三个方法已经确认不是最优解（也就是说和没答一样，“小题”就是如此残酷）
1 另外存放一个二叉排序树，每次插入时遍历二叉树。

2 另外存放一个排序数组，每次插入时二分查找。

3 另外存放一个数组或bitmap，每次产生一个数字对应的下标置1，快速查看是否已存在。

经过查资料，貌似需要洗牌算法。
我的理解，洗牌算法就是将一堆数字打乱，这样的话，和这道题有什么联系？

bruceteen

你将要求说清楚点

若“a[1000]数组， 用随机函数随机生成1000次填充”，就直接for循环啦
若再加上“不允许重复”，用 set 或 unordered_set 之类
若再加上“填充0到999，不允许重复”，看 std::random_shuffle

317358117

如果是0~999打乱的话可以这样

1. 
   
2. for(i = 0; i < 1000; i++) { a[i] = i; }
   
3. 
   
4. for(i = 0; i < 999; i++) {
   
5.     k = rand() % (1000-i);
   
6.     swap(a[i], a[i+k]);
   
7. }

复制代码

如果是值是随机的，可以随机一个数a作为起始，每次随机增量与起始相加得到b，然后再a=b，可以得到升序的随机序列

zhendehaoren

多谢ls，完全看不懂，不过即使这样，复杂度也得是o（2n）

如果采用第三种方法，o（n）就行了

cobras

又没说数的范围。若范围是32位整数，则可以将这个区间1000等分，每个区间取个随机数填充即可，复杂度o（n）

hanxin83

zhendehaoren 发表于 2014-10-17 14:42
多谢ls，完全看不懂，不过即使这样，复杂度也得是o（2n）

如果采用第三种方法，o（n）就行了

这楼可是标准的洗牌算法哦, 先得初始化一遍, 总得先有1000张牌么不是.

另外, 题目说是"随机生成1000次填充", 如果出现重复就不满足"1000次"这个硬性需求了.
没有指明数值范围, 那灵活性太大了, 自己想办法不让它重复罢了.

感觉题目出得不好.

socay2

5楼 区间等分  给个赞

bskay

等分还不如这样呢:
for (i = 0; i < 1000; i++)
{
     a = i*1000+(rand()%1000);
}


上面看起来不太像随机数,哪能相隔那么多啊,其实只要考虑到i作为一个因素就可以了,但是不能让它过大的影响数的分布
要降低它的"贡献值",可以参考取hash值的函数那样移位啊与啊和啊的..就能保证唯一,也不需要查有序表

xdsnet

如果要真正的随机数，则不能洗牌算法吧
应该是类似楼主3的算法，不过这个算法存在不能结束收敛的可能，所以不是复杂度最低的算法，这时如果单纯考虑降低复杂度，其实可以考虑一个移位+后续位算法，绝对不存在重复（纯理论，在支持大数乘法——长整数的条件下），可以实现O(1)，rand（）表示取一个随机整数。
步进一个计数器n
填充到数组中的过程
for (n=0;n<1000;n++){
a[n]=rand()*1000+n;
}
因为后3个十进制位肯定不同，所以这个算法填充的随机数不会重复的。

其实和楼上的差不多效果（我开始是没有看见楼上的），但性质不同，楼上的随机数范围要小很多的，这个理论取值范围是[0,max(rand())*1000+999]，楼上的取值范围是[0,999999]，而且填充是肯定的升序，我的排序是不固定的。可以通过rand（）的设计控制范围（比如用不到长整数）。