[LeetCode][519. 随机翻转矩阵] 2种方法：暴力法 和 降维 + 哈希表

By Long Luo

Leetcode 519. 随机翻转矩阵 题目如下：

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 <= 10^4
每次调用flip 时，矩阵中至少存在一个值为0的格子。
最多调用1000次flip和reset方法。

这道题和 384. 打乱数组 类似，考察的都是随机数的有用，下面我们用暴力法和哈希表 $2$ 种方法来解决这个问题。

方法一：暴力 + 随机数

思路与算法：

首先就想到的是新建一个矩阵 $\textit{matrix}$，调用 $\texttt{reset()}$ 时重置 $\textit{matrix}$。

但是调用 $\texttt{flip()}$ 呢？

1. 生成一个 $0$ 到 $\textit{total}$ 的随机数 $\textit{seed}$；
2. 如果当前数组元素值为 $1$，说明已经被调用过，需要重新生成一个随机数，返回上一步；
3. 如果当前数组元素值为 $0$，对其置 $1$，返回当前位置。

代码如下所示：

class 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$ 的空间来存储矩阵。

方法二：降维 + 哈希表记录交换

思路与算法：

方法一需要新建一个二维数组，而 $m$ 和 $n$ 都是 $10^4$，乘起来是 $10^8$，维护如此之大的数组是非常耗费内存和时间的。有没有什么方法可以优化呢？

注意到最多调用 $1000$ 次 $\texttt{flip()}$ 和 $\texttt{reset()}$ 方法，那么有没有办法可以只记录已经用过的数，还记得 384. 打乱数组 中洗牌算法中是如何交换数的吗？

将矩阵转换为一个长度为 $m \times n$ 的一维数组 $\textit{map}$，对于矩阵中的位置 $(i, j)$，它对应了 $\textit{map}$中的元素 $\textit{map}[i \times n + j]$，这样就保证了矩阵和 $map$ 的元素映射。在经过 $m \times n - k$ 次翻转 $\texttt{flip}$ 后，我们会修改 $\textit{map}$ 与矩阵的映射，使得当前矩阵中有 $m \times n - k$ 个 $1$ 和 $k$ 个 $0$。

使用一个 $\texttt{HashMap}$ 存储那些 $\textit{map}$ 中那些被修改了的映射。

对于一个数 $x$：

1. 如果 $x$ 不是 $\texttt{HashMap}$ 中的一个键，那么它直接映射到最开始的 $(x/n, x \mod n)$；

2. 如果 $x$ 是 $\texttt{HashMap}$ 中的一个键，那么它映射到其在 $\texttt{HashMap}$ 中对应的值。

实际运行中 $\texttt{HashMap}$ 的大小仅和翻转次数成正比，因为每一次翻转操作我们会交换 $\textit{map}$ 中两个元素的映射，即最多有两个元素的映射关系被修改。

代码如下所示：

static class Solution {
    int row;
    int col;
    int total;
    Map<Integer, Integer> map;
    Random random = new Random();

    public Solution(int m, int n) {
        row = m;
        col = n;
        map = new HashMap<>();
        total = row * col;
    }

    public int[] flip() {
        int x = random.nextInt(total);
        total--;
        int idx = map.getOrDefault(x, x);
        map.put(x, map.getOrDefault(total, total));
        return new int[]{idx / col, idx % col};
    }

    public void reset() {
        map.clear();
        total = row * col;
    }
}

复杂度分析：

• 时间复杂度：

  • $\texttt{flip}$：$O(1)$。
  • $\texttt{reset}$：$O(F)$，其中 $F$ 是在上一次 $\texttt{reset}()$ 之后执行 $\texttt{flip}()$ 的次数。

• 空间复杂度：$O(F)$，其中 $F$ 代表执行函数 $\texttt{flip}()$ 的次数。

---

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗