随机算法

Java Random类的常见用法

https://blog.csdn.net/qq_39754721/article/details/94736251

用 Rand7() 实现 Rand10()

随机范围扩展+拒绝采样
1）随机数范围扩展
已知 rand_N() 可以等概率的生成[1, N]范围的随机数
那么：
(rand_X() - 1) × Y + rand_Y() ==> 可以等概率的生成[1, X * Y]范围的随机数
即实现了 rand_XY()
所以(rand_7() - 1) × 7 + rand_7() ==> 可以等概率的生成[1, 49]范围的随机数
2）拒绝采样
只取[1, 40]范围内的数，否则继续随机生成；
[1, 40] - 1 得到 [0, 39]；
[0, 39] % 10得到[0, 9]；因为[0, 39]的40个数中，个位数为0/1/2/.../9的个数是一样的；
[0, 9] + 1得到[1, 10]

    public int rand10() {
        int number;
        do {
            number = (rand7() - 1) * 7 + rand7();
        } while (number > 40);
        return number % 10 + 1;
    }

打乱数组

• 每次随机从list中取一个数，并且remove这个数，直到所有数都取完。
• 时间复杂度为，因为list.remove操作是O(n)的时间复杂度。

class Solution {
    private int[] array;
    private int[] original;

    private Random rand = new Random();

    private List<Integer> getArrayCopy() {
        List<Integer> asList = new ArrayList<Integer>();
        for (int i = 0; i < array.length; i++) {
            asList.add(array[i]);
        }
        return asList;
    }

    public Solution(int[] nums) {
        array = nums;
        original = nums.clone();
    }
    
    public int[] reset() {
        array = original;
        original = original.clone();
        return array;
    }
    
    public int[] shuffle() {
        List<Integer> aux = getArrayCopy();

        for (int i = 0; i < array.length; i++) {
            int removeIdx = rand.nextInt(aux.size());
            array[i] = aux.get(removeIdx);
            aux.remove(removeIdx);
        }

        return array;
    }
}

** Fisher-Yates 洗牌算法**

• 对上面的暴力算法进行优化：第一次从(0, length)中选取一个数，与0互换，相当于随机取了一个数，放在0位置；下一轮从（1，length）中选取一个数（保证了上一轮中选取的数，在之后不会被选取到），与1互换；依次类推。这样就避免的remove操作

public class Solution {

    private int[] array;
    private int[] original;

    private Random random = new Random();

    private List<Integer> getArrayCopy() {
        List<Integer> asList = new ArrayList<Integer>();
        for (int i = 0; i < array.length; i++) {
            asList.add(array[i]);
        }
        return asList;
    }

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

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

    public int[] shuffle() {
        if (original.length == 0) {
            return new int[0];
        }
        for (int i = 0; i < array.length; i++) {
            int index = randRange(i, array.length);
            swap(i, index);
        }
        return array;
    }

    public int randRange(int min, int max) {
        return random.nextInt(max - min) + min;
    }

    public void swap(int index1, int index2) {
        int t = array[index1];
        array[index1] = array[index2];
        array[index2] = t;
    }

}

链表随机节点

public class Solution {
    private ListNode root;
    private Random random = new Random();

    public Solution(ListNode head) {
        this.root = head;
    }

    public int getRandom() {
        ListNode head = root;
        // 因为返回一个值 所以 蓄水池 容量为1
        // 蓄水池的水 就是 链表中的每个值.
        int[] res = {-1};
        int count = 0; // 水的数量
        boolean isFull = false; // 蓄水池是否已满
        while (head != null) {
            count++;  // 数量加1;
            if (!isFull) {
                res[0] = head.val;
                isFull = true; // 将蓄水池 灌满  设置isFull为true;
            } else {
                // 蓄水池代码的模板，直接套用。
                int i = random.nextInt(count);
                if (i < 1) {
                    res[0] = head.val;
                }
            }
            head = head.next;
        }
        return res[0];
    }

获取长度，生成随机数

    private ListNode head;
    private int length;
    private Random random = new Random();

    public Solution(ListNode head) {
        this.head = head;
        this.length = 0;
        ListNode ptr = head;
        while (ptr != null) {
            this.length++;
            ptr = ptr.next;
        }
    }

    public int getRandom() {
        int index = random.nextInt(length);
        ListNode ptr = head;
        while (index > 0) {
            ptr = ptr.next;
            index--;
        }
        return ptr.val;
    }

如果改成随机选K个节点的值，即蓄水池的水的容量为K，通用代码如下：

public class Solution {

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    private ListNode root;
    private Random random = new Random();

    public Solution(ListNode head) {
        this.root = head;
    }

    public int getRandom(int K) {
        ListNode head = root;

        int[] res = new int[K];
        int count = 0;
        boolean isFull = false;

        while (head != null) {
            count++;
            if (!isFull) {
                res[count - 1] = head.val;
                if (count == K) {
                    isFull = true;
                }
            } else {
                int i = random.nextInt(count);
                if (i < K) {
                    int index = new Random().nextInt(K);
                    res[index] = head.val;
                }
            }

            head = head.next;
        }
        return res[0];
    }

}