519. 随机翻转矩阵 :「双指针」&「哈希 swap」

题目描述

这是 LeetCode 上的 519. 随机翻转矩阵 ，难度为 中等。

Tag : 「哈希表」、「双指针」

给你一个 m x nmxn 的二元矩阵 matrixmatrix，且所有值被初始化为 00。

请你设计一个算法，随机选取一个满足 matrix[i][j] == 0 的下标 (i, j)(i,j) ，并将它的值变为 11 。

所有满足 matrix[i][j] == 0 的下标 (i, j)(i,j) 被选取的概率应当均等。

尽量最少调用内置的随机函数，并且优化时间和空间复杂度。

实现 Solution 类：

• Solution(int m, int n) 使用二元矩阵的大小 mm 和 nn 初始化该对象
• int[] flip() 返回一个满足 matrix[i][j] == 0 的随机下标 [i, j] ，并将其对应格子中的值变为 11
• void reset() 将矩阵中所有的值重置为 00

示例：

输入
["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^41<=m,n<=104
• 每次调用 flip 时，矩阵中至少存在一个值为 00 的格子。
• 最多调用 1000 次 flip 和 reset 方法。

双指针

矩阵大小的数据范围为 10^4104，因此我们不能使用真实构建矩阵的做法来做，同时利用二维的坐标能够唯一对应出编号（idx = row * n + colidx=row∗n+col），可以将问题转换为一维问题。

一个最为朴素的做法是利用调用次数只有 10^3103，我们可以在 [0, m * n）[0,m∗n） 范围内随机出一个下标 idxidx（对应矩阵的某个具体位置），然后从 idxidx 往两边进行扫描，找到最近一个未被使用的位置，将其进行标记翻转并返回。

该做法相比于一直随机的「拒绝采样」做法，能够确保单次 flip 操作中只会调用一次随机方法，同时利用矩阵只有 10^3103 个位置被翻转，因而复杂度上具有保证。

代码：

class Solution {
    int m, n;
    Set<Integer> set = new HashSet<>();
    Random random = new Random(300);
    public Solution(int _m, int _n) {
        m = _m; n = _n;
    }
    public int[] flip() {
        int a = random.nextInt(m * n), b = a;
        while (a >= 0 && set.contains(a)) a--;
        while (b < m * n && set.contains(b)) b++;
        int c = a >= 0 && !set.contains(a) ? a : b;
        set.add(c);
        return new int[]{c / n, c % n};
    }
    public void reset() {
        set.clear();
    }
}
复制代码

• 时间复杂度：令最大调用次数为 C = 1000C=1000，即矩阵中最多有 CC 个位置被翻转。flip 操作的复杂度为 O(C)O(C)；reset 复杂度为 O(C)O(C)
• 空间复杂度：O(C)O(C)

哈希表 + swap

在解法一中，我们将二维问题转化为了一维问题。

起始时，我们只需要在 [0, m * n)[0,m∗n) 这连续一段的区间内进行随机，但当我们经过了多次翻转后，该区间内的某些位置会被断开，使得数组不再连续。

如果我们希望在每次随机时都采用起始的方式（在连续一段内进行随机），需要确保某些位置被翻转后，剩余位置仍是连续。

具体的，我们可以使用「哈希表」多记录一层映射关系：起始时所有位置未被翻转，我们规定未被翻转的位置其映射值为编号本身（idx = row * n + colidx=row∗n+col），由于未被翻转的部分具有等值映射关系，因此无须在哈希表中真实存储。当随机到某个位置 idxidx 时，进行分情况讨论：

• 该位置未被哈希表真实记录（未被翻转）：说明 idxidx 可被直接使用，使用 idxidx 作为本次随机点。同时将右端点（未被使用的）位置的映射值放到该位置，将右端点左移。确保下次再随机到 idxidx，仍能直接使用 idxidx 的映射值，同时维护了随机区间的连续性；
• 该位置已被哈希表真实记录（已被翻转）：此时直接使用 idxidx 存储的映射值（上一次交换时的右端点映射值）即可，然后用新的右端点映射值将其进行覆盖，更新右端点。确保下次再随机到 idxidx，仍能直接使用 idxidx 的映射值，同时维护了随机区间的连续性。

代码：

class Solution {
    int m, n, cnt; // cnt 为剩余数个数，同时 cnt - 1 为区间右端点位置
    Map<Integer, Integer> map = new HashMap<>();
    Random random = new Random(300);
    public Solution(int _m, int _n) {
        m = _m; n = _n; cnt = m * n;
    }
    public int[] flip() {
        int x = random.nextInt(cnt--);
        int idx = map.getOrDefault(x, x);
        map.put(x, map.getOrDefault(cnt, cnt));
        return new int[]{idx / n, idx % n};
    }
    public void reset() {
        cnt = m * n;
        map.clear();
    }
}
复制代码

• 时间复杂度：令最大调用次数为 C = 1000C=1000，即矩阵中最多有 CC 个位置被翻转。flip 操作的复杂度为 O(1)O(1)；reset 复杂度为 O(C)O(C)
• 空间复杂度：O(C)O(C)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.519 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。