O(1) 随机插入删除与打乱数组

O(1) 随机插入删除（LeetCode 380）

class RandomizedSet {
    private Map<Integer, Integer> map = new HashMap<>();  // val -> index in list
    private List<Integer> list = new ArrayList<>();
    private Random rand = new Random();

    public boolean insert(int val) {
        if (map.containsKey(val)) return false;
        map.put(val, list.size());
        list.add(val);
        return true;
    }

    public boolean remove(int val) {
        if (!map.containsKey(val)) return false;
        int idx = map.get(val);
        int last = list.getLast();
        list.set(idx, last);      // 用最后一个元素填补空缺
        map.put(last, idx);
        list.removeLast();
        map.remove(val);
        return true;
    }

    public int getRandom() {
        return list.get(rand.nextInt(list.size()));
    }
}

关键：删除时用最后一个元素填补，避免数组移位，保证 O(1)。

允许重复的随机集合（LeetCode 381）

允许插入重复元素，每个值在 map 中存下标集合（HashSet）。

class RandomizedCollection {
    private Map<Integer, Set<Integer>> map = new HashMap<>();
    private List<Integer> list = new ArrayList<>();
    private Random rand = new Random();

    public boolean insert(int val) {
        boolean absent = !map.containsKey(val) || map.get(val).isEmpty();
        map.computeIfAbsent(val, k -> new HashSet<>()).add(list.size());
        list.add(val);
        return absent;
    }

    public boolean remove(int val) {
        if (!map.containsKey(val) || map.get(val).isEmpty()) return false;
        int removeIdx = map.get(val).iterator().next();
        map.get(val).remove(removeIdx);
        int last = list.getLast();
        if (removeIdx != list.size() - 1) {
            list.set(removeIdx, last);
            map.get(last).remove(list.size() - 1);
            map.get(last).add(removeIdx);
        }
        list.removeLast();
        return true;
    }

    public int getRandom() {
        return list.get(rand.nextInt(list.size()));
    }
}

打乱数组（LeetCode 384）

Fisher-Yates 洗牌算法：从后往前，每次随机选前面的元素与当前交换。

class Solution {
    private int[] original;
    private int[] arr;
    private Random rand = new Random();

    public Solution(int[] nums) {
        original = nums.clone();
        arr = nums.clone();
    }

    public int[] reset() {
        arr = original.clone();
        return arr;
    }

    public int[] shuffle() {
        for (int i = arr.length - 1; i > 0; i--) {
            int j = rand.nextInt(i + 1);
            int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
        }
        return arr;
    }
}

均匀性证明：每个排列出现的概率为 1/n!。

蓄水池抽样（Stream 中随机选 k 个）

// 从未知长度的流中等概率选1个
public int reservoirSampling(int[] stream) {
    int result = stream[0];
    Random rand = new Random();
    for (int i = 1; i < stream.length; i++) {
        if (rand.nextInt(i + 1) == 0) result = stream[i];
    }
    return result;
}