[LeetCode][519. 随机翻转矩阵] 2种方法：暴力法 和 降维 + 哈希表
By Long Luo
Leetcode 519. 随机翻转矩阵 题目如下：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
30519. 随机翻转矩阵
给你一个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 <= 10^4
每次调用flip 时，矩阵中至少存在一个值为0的格子。
最多调用1000次flip和reset方法。
这道题和 384. 打乱数组 类似，考察的都是随机数的有用，下面我们用暴力法和哈希表 \(2\) 种方法来解决这个问题。
方法一：暴力 + 随机数
思路与算法：
首先就想到的是新建一个矩阵 \(\textit{matrix}\)，调用 \(\texttt{reset()}\) 时重置 \(\textit{matrix}\)。
但是调用 \(\texttt{flip()}\) 呢？
- 生成一个 \(0\) 到 \(\textit{total}\) 的随机数 \(\textit{seed}\)；
- 如果当前数组元素值为 \(1\)，说明已经被调用过，需要重新生成一个随机数，返回上一步；
- 如果当前数组元素值为 \(0\)，对其置 \(1\)，返回当前位置。
代码如下所示：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
32class Solution {
int[][] matrix;
int row;
int col;
int total;
Random random = new Random();
public Solution(int m, int n) {
matrix = new int[m][n];
row = m;
col = n;
total = row * col;
}
public int[] flip() {
int rand = random.nextInt(total);
while (matrix[rand / col][rand % col] == 1) {
rand = random.nextInt(total);
}
matrix[rand / col][rand % col] = 1;
return new int[]{rand / col, rand % col};
}
public void reset() {
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
matrix[i][j] = 0;
}
}
}
}
复杂度分析：
- 时间复杂度：
- \(\texttt{flip}\)：\(O(mn)\)。
- \(\texttt{reset}\)：\(O(mn)\)。
- 空间复杂度：\(O(mn)\)，需要 \(mn\) 的空间来存储矩阵。