LeetCode题练习与总结：随机翻转矩阵--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]，并将其对应格子中的值变为1void 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方法。
二、解题思路
- 使用一个哈希表来记录已经被翻转的坐标，这样可以避免在矩阵中直接修改值，减少空间复杂度。
- 使用一个变量来记录当前总共剩余的可翻转的坐标数量。
- 在
flip()方法中，生成一个随机数，代表从剩余的可翻转坐标中随机选择一个。然后，将该坐标从哈希表中移除，并在返回坐标的同时将其标记为已翻转。 - 在
reset()方法中，清空哈希表，并重置剩余可翻转坐标的数量。
三、具体代码
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
class Solution {
private int m;
private int n;
private int remaining;
private Map<Integer, Integer> flipped;
private Random random;
public Solution(int m, int n) {
this.m = m;
this.n = n;
this.remaining = m * n;
this.flipped = new HashMap<>();
this.random = new Random();
}
public int[] flip() {
// 生成一个随机数
int randIndex = random.nextInt(remaining);
// 计算实际的坐标
int actualIndex = randIndex;
for (int key : flipped.keySet()) {
if (randIndex >= key) {
actualIndex++;
} else {
break;
}
}
int i = actualIndex / n;
int j = actualIndex % n;
// 记录该坐标已经被翻转
flipped.put(actualIndex, actualIndex);
// 减少剩余可翻转的数量
remaining--;
return new int[]{i, j};
}
public void reset() {
flipped.clear();
remaining = m * n;
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(m, n);
* int[] param_1 = obj.flip();
* obj.reset();
*/
这个实现中，我们通过哈希表 flipped 来记录已经被翻转的坐标的索引（而不是坐标本身），这样可以避免在矩阵中直接修改值，从而节省空间。每次调用 flip() 时，我们通过随机数生成器选择一个未被翻转的坐标，并将其记录下来。调用 reset() 时，我们清空哈希表并重置剩余可翻转坐标的数量。这样，我们保证了每次调用 flip() 时，每个未被翻转的坐标被选中的概率是相等的。
四、时间复杂度和空间复杂度
1. 时间复杂度
Solution(int m, int n)构造函数的时间复杂度是 O(1)，因为它只执行了几个赋值操作。flip()方法的时间复杂度在最坏情况下是 O(m * n)。这是因为我们需要遍历flipped哈希表来找到实际的下标。在最坏的情况下，即当所有的坐标都已经被翻转过，哈希表的大小将接近 m * n，因此我们需要遍历整个哈希表来找到未被翻转的坐标。每次调用flip()时，最坏情况下需要遍历整个哈希表。reset()方法的时间复杂度是 O(m * n)，因为我们需要清空哈希表，这将遍历所有的元素并释放它们。
2. 空间复杂度
Solution(int m, int n)构造函数的空间复杂度是 O(1)，因为它只存储了几个整型变量和一个哈希表，但哈希表此时为空。flip()方法本身不占用额外的空间，但是随着方法的多次调用，flipped哈希表会逐渐增长。在最坏的情况下，即当所有的坐标都被翻转过，哈希表将包含 m * n 个条目。因此，空间复杂度是 O(m * n)。reset()方法不占用额外的空间，它只是重置了哈希表和remaining变量。
综上所述，对于整个 Solution 类：
- 时间复杂度：构造函数 O(1)，
flip()方法 O(m * n)，reset()方法 O(m * n)。 - 空间复杂度：O(m * n)，这是由于
flipped哈希表在最坏情况下可能包含 m * n 个条目。
请注意，虽然 flip() 方法在最坏情况下的时间复杂度是 O(m * n)，但是在实际应用中，由于每次调用 flip() 都会减少一个可翻转的坐标，因此平均情况下，flip() 方法的时间复杂度会低于 O(m * n)。实际上，平均时间复杂度更接近于 O(1)，因为大多数情况下，我们不需要遍历整个哈希表。然而，在最坏情况下，即当所有的坐标都被翻转过，我们确实需要遍历整个哈希表，因此最坏情况下的时间复杂度仍然是 O(m * n)。
五、总结知识点
-
类定义：
class关键字用于定义一个类。- 类可以有成员变量和方法。
-
成员变量：
- 成员变量（字段）是在类的所有方法之外声明的变量，它们可以在类的任何方法中使用。
private关键字用于声明私有成员变量，它们只能在类的内部访问。
-
构造函数：
- 构造函数是一种特殊的方法，用于创建类的实例时初始化对象。
- 构造函数的名称必须与类名相同。
-
方法：
- 方法是类中定义的函数，用于执行特定操作。
public关键字用于声明公共方法，它们可以被类的实例外部访问。
-
数据结构：
HashMap是一种基于哈希表的映射数据结构，用于存储键值对。Map是一个接口，提供了操作键值对的方法。
-
随机数生成：
Random类用于生成伪随机数。nextInt(int bound)方法用于生成一个介于 0（包含）和指定值（不包含）之间的随机整数。
-
算术运算：
- 使用基本的算术运算符（
+,-,*,/,%）进行数学计算。
- 使用基本的算术运算符（
-
逻辑控制：
- 使用
for循环遍历集合。 - 使用
if-else语句进行条件判断。
- 使用
-
方法重置：
reset()方法用于将对象的状态重置为初始状态。
-
方法返回值：
- 方法可以返回一个值，使用
return关键字。
- 方法可以返回一个值，使用
-
数组：
- 使用数组来存储多个值，例如返回坐标。
以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。