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

发表于 2021-11-27 更新于 2024-03-05 分类于 Leetcode Waline：阅读次数：本文字数： 3.4k 阅读时长 ≈ 3 分钟

By Long Luo

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()}\) 呢？

生成一个 \(0\) 到 \(\textit{total}\) 的随机数 \(\textit{seed}\)；
如果当前数组元素值为 \(1\)，说明已经被调用过，需要重新生成一个随机数，返回上一步；
如果当前数组元素值为 \(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\)：

如果 \(x\) 不是 \(\texttt{HashMap}\) 中的一个键，那么它直接映射到最开始的 \((x/n, x \mod n)\)；
如果 \(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. 😉😃💗