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 方法。

解題思路

對于矩陣的每個位置都使用編號代替，編號范圍為[0,n*m-1]，使用set存儲已經被標記為1的位置，每次我們生成一個該區間內的隨機數，檢查該編號對應的位置是否為1，如果為1的話，則重新生成隨機數，否則返回該隨機數對應矩陣位置的下標，并且加入set中。

代碼

class Solution {
public:int mm,nn;unordered_set<int> set;Solution(int m, int n) {this->mm=m;this->nn=n;}vector<int> flip() {int cur=rand()%(nn*mm);while (set.count(cur)>0){cur=rand()%(nn*mm);}set.insert(cur);return {cur/nn,cur%nn};}void reset() {set.clear();}
};
/*** Your Solution object will be instantiated and called as such:* Solution* obj = new Solution(m, n);* vector<int> param_1 = obj->flip();* obj->reset();*/