?LeetCode刷題實戰(zhàn)519：隨機翻轉(zhuǎn)矩陣
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.
Solution(int m, int n) 使用二元矩陣的大小 m 和 n 初始化該對象
int[] flip() 返回一個滿足 matrix[i][j] == 0 的隨機下標 [i, j] ，并將其對應(yīng)格子中的值變?yōu)?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] 的概率應(yīng)當相同
solution.flip(); // 返回 [2, 0]，因為 [1,0] 已經(jīng)返回過了，此時返回 [2,0] 和 [0,0] 的概率應(yīng)當相同
solution.flip(); // 返回 [0, 0]，根據(jù)前面已經(jīng)返回過的下標，此時只能返回 [0,0]
solution.reset(); // 所有值都重置為 0 ，并可以再次選擇下標返回
solution.flip(); // 返回 [2, 0]，此時返回 [0,0]、[1,0] 和 [2,0] 的概率應(yīng)當相同
解題
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; // 隨機數(shù)對應(yīng)的值, 沒的話就對應(yīng)本身
????????S[r] = S.count(remain) ? S[remain] : S[remain] = remain; // remain是下次需要刪除的所以可以把這個值存到S[r]上，因為r已經(jīng)被使用了
????????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{}()};
};