LeetCode刷题实战519：随机翻转矩阵-技术圈

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 随机翻转矩阵，我们先来看题面：

https://leetcode-cn.com/problems/random-flip-matrix/

There is an m x n binary grid matrix with all the values set 0 initially. Design an algorithm to randomly pick an index (i, j) where matrix[i][j] == 0 and flips it to 1. All the indices (i, j) where matrix[i][j] == 0 should be equally likely to be returned.

Optimize your algorithm to minimize the number of calls made to the built-in random function of your language and optimize the time and space complexity.

Implement the Solution class:

Solution(int m, int n) Initializes the object with the size of the binary matrix m and n.
int[] flip() Returns a random index [i, j] of the matrix where matrix[i][j] == 0 and flips it to 1.
void reset() Resets all the values of the matrix to be 0.

给你一个 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.随机产生[0, remain - 1]来保证uniform distribution，每次抽完把抽中的数跟remain交换, 因为remain不可能再被抽中了

2.但是初始化和reset一维数组需要O(nr * nc) @ 解决方法: 哈希表 O(1)

-- 初始化和reset时直接clear()

-- 只有抽到时才会生成

class Solution {
public:
    Solution(int n_rows, int n_cols) {
        nr = n_rows, nc = n_cols, remain = nr * nc;
    }

    vector<int> flip() {
        uniform_int_distribution<int> uni(0, -- remain);
        int r = uni(rng); 
        int x = S.count(r) ? S[r] : S[r] = r; // 随机数对应的值, 没的话就对应本身
        S[r] = S.count(remain) ? S[remain] : S[remain] = remain; // remain是下次需要删除的所以可以把这个值存到S[r]上，因为r已经被使用了
        return {x / nc, x % nc};
    }

    void reset() {
        S.clear();
        remain = nr * nc;
    }
private:
    unordered_map<int, int> S;
    int nr, nc, remain;
    mt19937 rng{random_device{}()};
};