Java 產生不重覆亂數

Lab的人要我給他一個產生不重覆亂數的方法，下面是兩種方式，第一種很慢，速度是O(n^2)被幹詰到死XDD

Java要產生亂數很簡單，只要呼叫Random類別就可以了，不過如果想要不重覆的亂數，有一些小方法可以用，這裡提供兩種方法：

(1) 暴力比對法
這個getRan方法會接收一個整數，表示你要取得亂數的範圍，丟進去100表示你要取0~99之間的亂數

這個方法接收一個整數，表示你要取得亂數的最大範圍，呼叫 generateDuplicateRan(100) 則會回傳一個長度100的整數陣列，裡面就是0~99不重覆的整數。寫的方式很直覺，第一個for loop跑100次，每塞一個值就會去比對之前在陣列中的數字，如果相同就移除。缺點就是要產生大量亂數的時候很慢，因為有兩層for loop，速度是n^2，如果只是要少量亂數的人可以參考。

(2) Collection移出法
第二種方法就快多了，尤其在產生大量亂數的時候更為明顯。分成三個部分來解釋：

• 產生一個ArrayList，並且利用for loop塞值進去，你想要產生0~99的亂數，就丟100進去，他就會依序把0~99塞到ArrayList裡面。

• 這個部份就是trick所在，裡用Collection的remove method，隨機的取index，並且移出，直到ArrayList的size = 0。因為本來在ArrayList裡面的數字就沒有重複(用for loop塞的)，所以隨機取出的值也不會重複。
  
  
• 最後一個部份就是去呼叫上面的方法並且宣告一個array來接收上面產生的亂數。
  

[UPDATE 2009/04/07]
強者我同學bluesway寫了一個比我快的版本(我也沒有覺得我的很快啦...)，用的資料結構是Hash，大家可以參考XD