Java 生成指定範圍不重複隨機數的多種算法對比與優化

問題描述

生成 [1, 100] 範圍內 n 個不重複隨機整數，常見於抽獎、測試數據、洗牌等場景。

算法 1：List + contains 檢查（O(n²)）

List<Integer> list = new ArrayList<>();
Random r = new Random();
while (list.size() < n) {
    int num = r.nextInt(100) + 1;
    if (!list.contains(num)) list.add(num); // 線性查找
}

缺點：隨著數據增長，contains 越來越慢，總體 O(n²)。

算法 2：數組 + 雙重循環去重（O(n²)）

int[] arr = new int[n];
Random r = new Random();
for (int i = 0; i < n; ) {
    int num = r.nextInt(100) + 1;
    boolean dup = false;
    for (int j = 0; j < i; j++) if (arr[j] == num) { dup = true; break; }
    if (!dup) arr[i++] = num;
}

同樣 O(n²)，且代碼冗長。

算法 3：HashSet 去重（O(n) 期望）

Set<Integer> set = new HashSet<>();
Random r = new Random();
while (set.size() < n) {
    set.add(r.nextInt(100) + 1); // HashSet 自動去重
}
Integer[] result = set.toArray(new Integer[0]);

優點：代碼簡潔，平均 O(1) 插入/查找。缺點：HashSet 佔用額外內存，極端情況下哈希衝突退化。

算法 4：Fisher-Yates 洗牌算法（O(n) 最優）

原理：初始化有序數組 [1..100]，隨機交換前 n 位元素。

int[] pool = new int[100];
for (int i = 0; i < 100; i++) pool[i] = i + 1;

Random r = new Random();
for (int i = 0; i < n; i++) {
    int idx = r.nextInt(100 - i) + i; // [i, 99]
    // 交換
    int tmp = pool[i];
    pool[i] = pool[idx];
    pool[idx] = tmp;
}
// 前 n 個即為結果
int[] result = Arrays.copyOf(pool, n);

優點：無重複保證、無額外空間、單次遍歷、均勻分佈。缺點：需預先分配全範圍數組，範圍極大（如 1~1億）時內存壓力大。

算法 5：Reservoir Sampling（流式/超大範圍）

當範圍極大無法全量加載時，保持固定大小水池：

int[] reservoir = new int[n];
Random r = new Random();
for (int i = 1; i <= 100; i++) {
    if (i <= n) {
        reservoir[i-1] = i;
    } else {
        int j = r.nextInt(i); // [0, i-1]
        if (j < n) reservoir[j] = i; // 以 n/i 概率替換
    }
}

適用於數據流、資料庫大表隨機抽樣。

效能對比（生成 10,000 個數，範圍 1~100,000）

代碼封裝：通用工具類

public final class RandomUtils {
    private static final Random RANDOM = new Random();

    /** Fisher-Yates：範圍 [min, max] 取 k 個不重複 */
    public static int[] distinctInts(int min, int max, int k) {
        if (k > max - min + 1) throw new IllegalArgumentException("k 超過範圍大小");
        int[] pool = new int[max - min + 1];
        for (int i = 0; i < pool.length; i++) pool[i] = min + i;
        for (int i = 0; i < k; i++) {
            int idx = RANDOM.nextInt(pool.length - i) + i;
            int tmp = pool[i];
            pool[i] = pool[idx];
            pool[idx] = tmp;
        }
        return Arrays.copyOf(pool, k);
    }

    /** Reservoir Sampling：超大範圍流式抽樣 */
    public static int[] reservoirSample(long rangeStart, long rangeEnd, int k) {
        long total = rangeEnd - rangeStart + 1;
        if (k > total) throw new IllegalArgumentException();
        int[] reservoir = new int[k];
        for (long i = 0; i < total; i++) {
            long val = rangeStart + i;
            if (i < k) reservoir[(int)i] = (int)val;
            else {
                long j = RANDOM.nextLong(total); // 需自行實現 nextLong(bound)
                if (j < k) reservoir[(int)j] = (int)val;
            }
        }
        return reservoir;
    }
}

結語

日常開發中，範圍較小（<100萬）首選 Fisher-Yates，代碼簡單且效能最優；範圍極大或流式數據改用 Reservoir Sampling。切勿使用雙重循環去重，效能差且易出錯。