​LeetCode刷题实战519：随机翻转矩阵

今天和大家聊的问题叫做 随机翻转矩阵，我们先来看题面：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{}()};
};

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。