一道看似不起眼的小題

zhendehaoren

面試的時(shí)候最怕遇到“小題”

這次栽在了這樣的一道題上面：
a[1000]數(shù)組， 用隨機(jī)函數(shù)隨機(jī)生成1000次填充，不允許重復(fù)，也就是說不止1000次，復(fù)雜度最低實(shí)現(xiàn)

以下三個(gè)方法已經(jīng)確認(rèn)不是最優(yōu)解（也就是說和沒答一樣，“小題”就是如此殘酷）
1 另外存放一個(gè)二叉排序樹，每次插入時(shí)遍歷二叉樹。

2 另外存放一個(gè)排序數(shù)組，每次插入時(shí)二分查找。

3 另外存放一個(gè)數(shù)組或bitmap，每次產(chǎn)生一個(gè)數(shù)字對應(yīng)的下標(biāo)置1，快速查看是否已存在。

經(jīng)過查資料，貌似需要洗牌算法。
我的理解，洗牌算法就是將一堆數(shù)字打亂，這樣的話，和這道題有什么聯(lián)系？

bruceteen

你將要求說清楚點(diǎn)

若“a[1000]數(shù)組， 用隨機(jī)函數(shù)隨機(jī)生成1000次填充”，就直接for循環(huán)啦
若再加上“不允許重復(fù)”，用 set 或 unordered_set 之類
若再加上“填充0到999，不允許重復(fù)”，看 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. }

復(fù)制代碼

如果是值是隨機(jī)的，可以隨機(jī)一個(gè)數(shù)a作為起始，每次隨機(jī)增量與起始相加得到b，然后再a=b，可以得到升序的隨機(jī)序列

zhendehaoren

多謝ls，完全看不懂，不過即使這樣，復(fù)雜度也得是o（2n）

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

cobras

又沒說數(shù)的范圍。若范圍是32位整數(shù)，則可以將這個(gè)區(qū)間1000等分，每個(gè)區(qū)間取個(gè)隨機(jī)數(shù)填充即可，復(fù)雜度o（n）

hanxin83

zhendehaoren 發(fā)表于 2014-10-17 14:42
多謝ls，完全看不懂，不過即使這樣，復(fù)雜度也得是o（2n）

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

這樓可是標(biāo)準(zhǔn)的洗牌算法哦, 先得初始化一遍, 總得先有1000張牌么不是.

另外, 題目說是"隨機(jī)生成1000次填充", 如果出現(xiàn)重復(fù)就不滿足"1000次"這個(gè)硬性需求了.
沒有指明數(shù)值范圍, 那靈活性太大了, 自己想辦法不讓它重復(fù)罷了.

感覺題目出得不好.

socay2

5樓 區(qū)間等分  給個(gè)贊

bskay

等分還不如這樣呢:
for (i = 0; i < 1000; i++)
{
     a = i*1000+(rand()%1000);
}


上面看起來不太像隨機(jī)數(shù),哪能相隔那么多啊,其實(shí)只要考慮到i作為一個(gè)因素就可以了,但是不能讓它過大的影響數(shù)的分布
要降低它的"貢獻(xiàn)值",可以參考取hash值的函數(shù)那樣移位啊與啊和啊的..就能保證唯一,也不需要查有序表

xdsnet

如果要真正的隨機(jī)數(shù)，則不能洗牌算法吧
應(yīng)該是類似樓主3的算法，不過這個(gè)算法存在不能結(jié)束收斂的可能，所以不是復(fù)雜度最低的算法，這時(shí)如果單純考慮降低復(fù)雜度，其實(shí)可以考慮一個(gè)移位+后續(xù)位算法，絕對不存在重復(fù)（純理論，在支持大數(shù)乘法——長整數(shù)的條件下），可以實(shí)現(xiàn)O(1)，rand（）表示取一個(gè)隨機(jī)整數(shù)。
步進(jìn)一個(gè)計(jì)數(shù)器n
填充到數(shù)組中的過程
for (n=0;n<1000;n++){
a[n]=rand()*1000+n;
}
因?yàn)楹?個(gè)十進(jìn)制位肯定不同，所以這個(gè)算法填充的隨機(jī)數(shù)不會(huì)重復(fù)的。

其實(shí)和樓上的差不多效果（我開始是沒有看見樓上的），但性質(zhì)不同，樓上的隨機(jī)數(shù)范圍要小很多的，這個(gè)理論取值范圍是[0,max(rand())*1000+999]，樓上的取值范圍是[0,999999]，而且填充是肯定的升序，我的排序是不固定的。可以通過rand（）的設(shè)計(jì)控制范圍（比如用不到長整數(shù)）。