标签： 随机化

给你一个 m x n 的二元矩阵 matrix ，且所有值被初始化为 0 。请你设计一个算法，随机选取一个满足 matrix[i][j] == 0 的下标 (i, j) ，并将它的值变为 1 。所有满足 matrix[i][j] == 0 的下标 (i, j) 被选取的概率应当均等。

尽量最少调用内置的随机函数，并且优化时间和空间复杂度。

实现 Solution 类：

• Solution(int m, int n) 使用二元矩阵的大小 m 和 n 初始化该对象
• int[] flip() 返回一个满足 matrix[i][j] == 0 的随机下标 [i, j] ，并将其对应格子中的值变为 1
• void reset() 将矩阵中所有的值重置为 0

示例：

输入
["Solution", "flip", "flip", "flip", "reset", "flip"]
[[3, 1], [], [], [], [], []]
输出
[null, [1, 0], [2, 0], [0, 0], null, [2, 0]]

解释
Solution solution = new Solution(3, 1);
solution.flip();  // 返回 [1, 0]，此时返回 [0,0]、[1,0] 和 [2,0] 的概率应当相同
solution.flip();  // 返回 [2, 0]，因为 [1,0] 已经返回过了，此时返回 [2,0] 和 [0,0] 的概率应当相同
solution.flip();  // 返回 [0, 0]，根据前面已经返回过的下标，此时只能返回 [0,0]
solution.reset(); // 所有值都重置为 0 ，并可以再次选择下标返回
solution.flip();  // 返回 [2, 0]，此时返回 [0,0]、[1,0] 和 [2,0] 的概率应当相同

提示：

• 1 <= m, n <= 104
• 每次调用flip 时，矩阵中至少存在一个值为 0 的格子。
• 最多调用 1000 次 flip 和 reset 方法。

分析，实现，【掉坑】，改进

直接模拟，思路

1. 声明一个m * n的二维数组，随机翻转一个
2. 但是接下来的问题就是，如何随机保证横轴和纵轴的坐标的随机概率相等，所以我们可以换个思路，直接声明一个m * n长度的一维数组，在这个长度内随机，而每一个随机数都可以映射回原来的矩阵中，从而保证每一个格子的随机概率是相等的
3. 下一个问题，之前已经翻转到过的位置不能再随机到。
   • 那么我们就需要记录一下剩余多少位置可以随机，从而在这个范围内进行随机操作
   • 如果在这个范围内随机到的数字是之前原数组中已经翻转过的，那么就从这个位置开始一直往后找到未被翻转的过的那个位置
4. 最终将随机到的位置坐标重新映射回矩阵坐标中返回即可

代码

class Solution {

    int[] matrix;
    int m;
    int n;
    Random random;
    int total;

    public Solution(int m, int n) {
        random = new Random();
        this.m = m;
        this.n = n;
        reset();
    }
    
    public int[] flip() {
        int idx = random.nextInt(total);
        while (matrix[idx]==1){
            idx++;
        }
        total--;
        matrix[idx] = 1;
        return new int[]{idx/n,idx%n};
    }
    
    public void reset() {
        matrix = new int[m * n];
        total = matrix.length;
    }
}

提交，跑到第19个测试用例，报OOM了，看下入参是10000 * 10000，按照道理java中数组的最大长度根据具体数据类型和JVM配置实际情况应该是一个接近Integer.MAX_VALU - 8的值，最大就是这么多，此时OOM的话，必然应该是限制了内存大小了

那么我们不妨再换个思路，题面中给出了 最多调用 1000 次 flip 和 reset 方法，我们就可以不用记录整个数组的情况，而是换一种角度，只记录哪些位置被翻转过，使用一个HashSet来存储这些位置信息，那么修改后代码如下

代码

class Solution {

    int m;
    int n;
    Random random;
    int total;
    HashSet<Integer> hashSet;

    public Solution(int m, int n) {
        random = new Random();
        this.m = m;
        this.n = n;
        reset();
    }
    
    public int[] flip() {
        int idx = random.nextInt(total);
        while (hashSet.contains(idx)){
            idx++;
        }
        total--;
        hashSet.add(idx);
        return new int[]{idx/n,idx%n};
    }
    
    public void reset() {
        hashSet = new HashSet<>();
        total = m * n;
    }
}

给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。打乱后，数组的所有排列应该是 等可能 的。

实现 Solution class:

• Solution(int[] nums) 使用整数数组 nums 初始化对象
• int[] reset() 重设数组到它的初始状态并返回
• int[] shuffle() 返回数组随机打乱后的结果

示例 1：

输入
["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]
输出
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

解释
Solution solution = new Solution([1, 2, 3]);
solution.shuffle();    // 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。例如，返回 [3, 1, 2]
solution.reset();      // 重设数组到它的初始状态 [1, 2, 3] 。返回 [1, 2, 3]
solution.shuffle();    // 随机返回数组 [1, 2, 3] 打乱后的结果。例如，返回 [1, 3, 2]

提示：

• 1 <= nums.length <= 50
• -106 <= nums[i] <= 106
• nums 中的所有元素都是 唯一的
• 最多可以调用 104 次 reset 和 shuffle

随机简单，可以参考下java.util.Collections#shuffle方法

核心：和前面的随机一位数字交换

class Solution {

    int[] nums;

    int[] shuffle;

    public Solution(int[] nums) {
        this.nums = nums;
    }
    
    public int[] reset() {
        return nums;
    }

    
    public int[] shuffle() {
        shuffle = nums.clone();
        Random random = new Random();
        for (int i = 0; i < shuffle.length; i++) {
            swap(shuffle,i,random.nextInt(i+1));
        }
        return shuffle;
    }

    public void swap(int[] arr ,int x ,int y){
        int tmp = arr[x];
        arr[x] = arr[y];
        arr[y] = tmp;
    }

}

看下java.util.Collections#shuffle(java.util.List<?>, java.util.Random)方法的源码，其实思想是一样的

public static void shuffle(List<?> list, Random rnd) {
    int size = list.size();
    if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
        for (int i=size; i>1; i--)
            swap(list, i-1, rnd.nextInt(i));
    } else {
        Object arr[] = list.toArray();

        // Shuffle array
        for (int i=size; i>1; i--)
            swap(arr, i-1, rnd.nextInt(i));

        // Dump array back into list
        // instead of using a raw type here, it's possible to capture
        // the wildcard but it will require a call to a supplementary
        // private method
        ListIterator it = list.listIterator();
        for (int i=0; i<arr.length; i++) {
            it.next();
            it.set(arr[i]);
        }
    }
}

给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。

进阶:
如果链表十分大且长度未知，如何解决这个问题？你能否使用常数级空间复杂度实现？

示例:

// 初始化一个单链表 [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);

// getRandom()方法应随机返回1,2,3中的一个，保证每个元素被返回的概率相等。
solution.getRandom();

题解

简单啊，，，随机么。直接存成数组，然后一个

Math.random()

出来了

class Solution2 {

    List<ListNode> list;
    /** @param head The linked list's head.
    Note that the head is guaranteed to be not null, so it contains at least one node. */
    public Solution2(ListNode head) {
        list = new ArrayList<>();
        while (head!=null){
            list.add(head);
            head = head.next;
        }
    }

    /** Returns a random node's value. */
    public int getRandom() {
        int random = (int)(Math.random() * list.size());
        return list.get(random).val;
    }
}

进阶。不用总长度怎么取随机，最近好像遇到好几次了，特地花了点时间去仔细理解了下水塘抽样随机算法。本题题解如下

class Solution {

    ListNode head;
    Random random;
    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    public Solution(ListNode head) {
        this.head = head;
        random = new Random();
    }
    
    /** Returns a random node's value. */
    public int getRandom() {
        ListNode node = head;
        int count = 1;
        int val = node.val;
        while (node!=null){
            if (random.nextInt(count) == 1){
                val =node.val;
            }
            count++;
            node = node.next;
        }
        return val;
    }
}

给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。

实现 Solution class:

• Solution(int[] nums) 使用整数数组 nums 初始化对象
• int[] reset() 重设数组到它的初始状态并返回
• int[] shuffle() 返回数组随机打乱后的结果

示例：

输入
["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]
输出
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

解释
Solution solution = new Solution([1, 2, 3]);
solution.shuffle();    // 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。例如，返回 [3, 1, 2]
solution.reset();      // 重设数组到它的初始状态 [1, 2, 3] 。返回 [1, 2, 3]
solution.shuffle();    // 随机返回数组 [1, 2, 3] 打乱后的结果。例如，返回 [1, 3, 2]

提示：

• 1 <= nums.length <= 200
• -106 <= nums[i] <= 106
• nums 中的所有元素都是 唯一的
• 最多可以调用 5 * 104 次 reset 和 shuffle

题解

class Solution {

    int[] origin;
    int[] randArr;

    public Solution(int[] nums) {
        origin = nums;
        randArr = nums.clone();
    }
    
    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        randArr = origin.clone();
        return origin;
    }
    
    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        Random random = new Random();
        for (int i = 0; i < randArr.length; i++) {
            int randIndex = random.nextInt(i+1);
            int tmp = randArr[i];
            randArr[i] = randArr[randIndex];
            randArr[randIndex] = tmp;
        }
        return randArr;
    }
}

概率的东西有点陌生，高中大学的东西已经彻底全忘了，官方题解说的Fisher-Yates 洗牌算法也没太看懂，为啥这么洗完概率就一定是均等的。哎。。。挫败感。

昨天的每日一题

已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数，试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。

不要使用系统的 Math.random() 方法。

示例 1:

输入: 1
输出: [7]

示例 2:

输入: 2
输出: [8,4]

示例 3:

输入: 3
输出: [8,1,10]

提示:

1. rand7 已定义。
2. 传入参数: n 表示 rand10 的调用次数。

进阶:

1. rand7()调用次数的 期望值 是多少 ?
2. 你能否尽量少调用 rand7() ?

简单版

public int rand10() {
        int randA = rand7();
        int randB = rand7();
        if (randA >= 5 && randB <=3){
            return rand10();
        }
        return (randA+randB)%10 + 1;
    }

分析过程如下，和上次求质数LeetCode刷题【204】计数质数分析过程类似，先把结果都求出来，然后像是敲冰块游戏一样敲掉不需要的结果，剩下的就是我们需要的结果了。

第一步，rand7只能取到1-7的值，要求到1-10的话，那么至少也要两个rand7来相加的情况处理，那么对求和情况分析

那么可以看到，结果为8的概率最大，有7种可能，即7/49的概率。对图中结果再用10取余可以得到如下

如图中锁标示出来的那样，如果把右上角，或者右下角的情况扣掉的话，那么结果所有数值的概率都是4/40的概率。所以显而易见的代码就如上那样出来了。

另一个解法

class Solution extends SolBase {

    public int rand10() {
        int num = rand7();
        while (true) {
            num = (num-1) * 7 + rand7();
            if(num <= 40){
                return num % 10 +1;
            }
            return rand10();
        }
    }
}