今天是堅持每日一題打卡的第二十六天

---

題目鏈接：https://leetcode-cn.com/problems/random-flip-matrix/solution/

題解匯總：https://zhanglong.blog.csdn.net/article/details/121071779

---

題目描述

給你一個 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 方法。

---

思路：數組降維 + 哈希Swap防止中斷。

一個比較好的題解：https://leetcode-cn.com/problems/random-flip-matrix/solution/geekplayers-leetcode-ac-yi-kan-jiu-dong-hktin/

---

class Solution { private:int m, n, len;unordered_map<int, int>um; public:Solution(int m, int n) {this->m = m;this->n = n;this->len = m * n;}vector<int> flip() {int key = rand() % len;int val = key;if (um.count(key)) { // 如果映射存在值，則證明不是 x->xval = um[key];}// 如果um[len-1]存在，則把該值移動到um[tmp]上， 如果um[len-1]不存在，則把len-1移動到um[tmp]上if (um.count(len-1)) {um[key] = um[len-1];um.erase(len-1);} else {um[key] = len-1;}len--;int row = val / n;int col = val % n;return {row, col};}void reset() {len = m * n;um.clear();} };

總結

以上是生活随笔為你收集整理的【解题报告】Leecode 519. 随机翻转矩阵——Leecode每日一题系列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。