Java 不重複隨機抽樣算法全解析：從暴力到 Floyd 算法

問題定義

在區間 [start, end] 中隨機抽取 count 個不重複整數，要求時間/空間效率最優。

六大算法演進與複雜度對比

核心代碼：迭代 Floyd 算法（生產級推薦）

import java.util.*;

public class FloydSampling {
    private static final Random RAND = new Random();

    /** 
     * @param start 區間起始（含）
     * @param end   區間結束（含）
     * @param count 抽樣數量，必須 ≤ end-start+1
     * @return 不重複隨機數列表，順序即抽樣順序
     */
    public static List<Integer> sample(int start, int end, int count) {
        if (count > end - start + 1) throw new IllegalArgumentException("count exceeds range");
        List<Integer> result = new ArrayList<>(count);
        for (int i = end - count + 1; i <= end; i++) {
            int r = start + RAND.nextInt(i - start + 1); // [start, i]
            if (result.contains(r)) {
                result.add(i); // 衝突：直接加入當前最大值 i
            } else {
                result.add(r);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        List<Integer>> sample = sample(1, 100, 10);
        System.out.println(sample); // 例：[7, 42, 15, 89, 3, 56, 22, 91, 11, 68]
    }
}

算法證明直觀理解

Floyd 算法本質是保留已選元素的有序集合，第 k 輪從 [start, end-count+k] 隨機，若衝突則選 end-count+k。數學歸納法可證明每個組合等概率 1/C(n,count)。

大數據場景優化：Reservoir Sampling

若總體 N 未知或極大（如流式數據），使用 水塘抽樣：

public static <T> List<T> reservoirSample(Iterator<T> data, int k) {
    List<T> reservoir = new ArrayList<>(k);
    int i = 0;
    while (data.hasNext()) {
        T item = data.next();
        if (i < k) reservoir.add(item);
        else {
            int r = RAND.nextInt(i + 1);
            if (r < k) reservoir.set(r, item);
        }
        i++;
    }
    return reservoir;
}

總結建議

• 已知範圍、count 較小 → 迭代 Floyd（O(count) 時間/空間）。
• 範圍極大（百萬級以上）但 count 小 → 仍用 Floyd，但改用 HashSet 存結果，contains 為 O(1)。
• 流式/未知總量 → Reservoir Sampling。
• 嚴禁 在生產環境使用暴力隨機或存在性檢查（O(n²) 會導致延遲抖動）。