友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
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方法。
思路分析
双指针。由于数字太大，无法保存所有的坐标点，所以构建未使用的坐标点，然后再删除行不通。反过来，记录已经使用的点，随机生成的坐标如果已经翻转，则向两边扩散，这样就可以保存更少的坐标，就能满足内存要求了。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-02-21 19:20:15
*/
class Solution {
int row;
int column;
Set<Integer> used;
Random random;
public Solution(int m, int n) {
row = m;
column = n;
random = new Random();
reset();
}
public int[] flip() {
int counter = row * column;
int a = random.nextInt(counter), b = a;
while (a >= 0 && used.contains(a)) {
a--;
}
while (b < counter && used.contains(b)) {
b++;
}
int c = a >= 0 && !used.contains(a) ? a : b;
used.add(c);
return new int[]{c / column, c % column};
}
public void reset() {
used = new HashSet<>();
}
}