概率 - 洗牌算法 - 《学习笔记》

519. 随机翻转矩阵">519. 随机翻转矩阵

洗牌的结果是所有元素的一个排列，一副牌如果有n张，最终的可能性是 n! 个。
一次公平的洗牌等价于等概率得到这 n! 结果中的任意一个。
还等价于每个位置出现每张牌的概率是相同的，都是 1 / n

时间复杂度： O(n)

Random r = new Random();
int[] a;    //一副待洗的牌
for (int i = n - 1; i >= 0; i--) {
     int idx = r.nextInt(i + 1);
    swap(a, i, idx);
}

519. 随机翻转矩阵

给你一个 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 方法。

思路：
我一开始的做法是模仿洗牌算法，创建一个n*m的数组将二维映射到一维，进行一轮洗牌，每次从中顺序取一张，当取完后再次进行洗牌。
但是这种做法的问题是空间太大，直接爆了。
换种思路，每次从牌堆里取一张，只需要记录剩余的牌有哪些即可，用哈希表就可以（又学会一种哈希表的妙用！）
例如：初始大小为5
[0, 1, 2, 3, 4] 第一轮：从[0, 4]中任选一个数字，如果是洗牌算法，相当于任选一个下标i后，交换i与当前下标j的值。用哈希实现相当于交换两个键对应的值并返回j对应的值。假设选了3，此处返回的就是交换前键为3对应的值，也就是3
[0, 1, 2, 4, x] 取出3之后，3现在对应的值应该变为当前正在取的键所对应的值，也就是4。之后4对应的键值对在本轮永远不会被选到。
[0, 1, 2, 4] 第二轮：从 [0, 2]中任选一个数字，假设选择了1，交换键0和键2对应的值得到[0, 4, 2, 1]并返回键2对应的值1
[0, 4, 2]
…

class Solution {
    int n, m, tot;
    Map<Integer, Integer> map = new HashMap<>();
    public Solution(int n, int m) {
        this.n = n;
        this.m = m;
        tot = n * m;
    }
    public int[] flip() {
        tot--;
        int j = tot;
        int i = new Random().nextInt(j + 1);
        int res = map.getOrDefault(i, i);
        map.put(i, map.getOrDefault(j, j));
        return new int[]{res / m, res % m};
    }
    public void reset() {
        map.clear();
        tot = n * m;
    }
}
/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(m, n);
 * int[] param_1 = obj.flip();
 * obj.reset();
 */