不重復(fù)隨機(jī)數(shù)列生成算法

1、不重復(fù)隨機(jī)數(shù)列生成算法本文將講述一個(gè)高效的不重復(fù)隨機(jī)數(shù)列的生成算法，其效率比通常用 hashtable 消重的方法要快很多。作者：eaglet轉(zhuǎn)載請(qǐng)注明出處。首先我們來(lái)看命題：給定一個(gè)正整數(shù)n需要輸出一個(gè)長(zhǎng)度為n的數(shù)組，數(shù)組元素是隨機(jī)數(shù)，范圍為 0 - n-1，且元素不能重復(fù)。比如n = 3時(shí)，需要獲取一個(gè)長(zhǎng)度為3的數(shù)組， 元素范圍為0-2，比如 0,2,1 。這個(gè)問(wèn)題的通常解決方案就是設(shè)計(jì)一個(gè) hashtable ，然后循環(huán)獲取隨機(jī)數(shù)，再 到hash table中找，如果hash table中沒(méi)有這個(gè)數(shù)，則輸出。下面給出這種算 法的代碼public static int GetRandomS

2、equenceO(int total)int hashtable = new inttotal;int output 二 new inttotal;Random random = new Random。；for (int i 二 0; i 0)num = random.Nex t(0, tot al);outputi二 num;hashtablenum = 1;return output;代碼很簡(jiǎn)單，從0到total - 1循環(huán)獲取隨機(jī)數(shù)，再去hash table中嘗試匹 配，如果這個(gè)數(shù)在 hashtable 中不存在，則輸出，并把這個(gè)數(shù)在 hashtable 中 置1，否則循環(huán)嘗試獲取隨機(jī)數(shù)

3、，直到找到一個(gè)不在 hashtable 中的數(shù)為止。這 個(gè)算法的問(wèn)題在于需要不斷嘗試獲取隨機(jī)數(shù)，在 hashtable 接近滿時(shí)，這個(gè)嘗 試失敗的概率會(huì)越來(lái)越高。那么有沒(méi)有什么算法，不需要這樣反復(fù)嘗試嗎？答案是肯定的。如上圖所示，我們?cè)O(shè)計(jì)一個(gè)順序的數(shù)組，假設(shè) n = 4第一輪，我們?nèi)? - 3之間的隨機(jī)數(shù)，假設(shè)為2,這時(shí)，我們把數(shù)組位置為2 的數(shù)取出來(lái)輸出，并把這個(gè)數(shù)從數(shù)組中刪除，這時(shí)這個(gè)數(shù)組變成了第二輪，我們?cè)偃?0-2 之間的隨機(jī)數(shù)，假設(shè)為1，并把這個(gè)位置的數(shù)輸出，同 時(shí)把這個(gè)數(shù)從數(shù)組刪除，以此類推，直到這個(gè)數(shù)組的長(zhǎng)度為0。這時(shí)我們就可以 得到一個(gè)隨機(jī)的不重復(fù)的序列。這個(gè)算法的好處是不需要

4、用一個(gè) hashtable 來(lái)存儲(chǔ)已獲取的數(shù)字，不需要反復(fù) 嘗試。算法代碼如下：public static int GetRandomSequencel(int total)List input 二 new List();for (int i 二 0; i total; i+)inp ut .Add(i);List output 二 new List();Random random = new Random();int end = total;for (int i 二 0; i / public static int GetRandomSequence2(int total)int seque

5、nce = new inttotal;int output 二 new inttotal;for (int i 二 0; i total; i+)sequencei = i;Random random = new Random();int end = total 1;for (int i 二 0; i total; i+)int num = random.Nex t(0, end + 1);outputi二 sequencenum; sequencenum = sequenceend; end;return output;下面是 n 等于 1 萬(wàn)，10 萬(wàn)和 100 萬(wàn)時(shí)的測(cè)試數(shù)據(jù)，時(shí)間單位為毫秒。從測(cè)試數(shù) 據(jù)看 GetRandomSequence2 的用時(shí)和 n 基本成正比，線性增長(zhǎng)的，這個(gè)和理論上 的算法復(fù)雜度O(n)也是一致的，另外兩個(gè)算法則隨著n的增大，用時(shí)超過(guò)了線 性增長(zhǎng)。在 1 百萬(wàn)時(shí)，我的算法比用 hashtable 的算法要快 10 倍以上。100001000