LC 519. 随机翻转矩阵

题目描述

这是 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] ，并将其对应格子中的值变为 $1$
  • void reset() 将矩阵中所有的值重置为 $0$

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入
["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 方法。

双指针

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

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

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

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 = 1000$，即矩阵中最多有 $C$ 个位置被翻转。flip 操作的复杂度为 $O(C)$；reset 复杂度为 $O(C)$
  • 空间复杂度：$O(C)$

哈希表 + swap

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

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

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

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

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

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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 = 1000$，即矩阵中最多有 $C$ 个位置被翻转。flip 操作的复杂度为 $O(1)$；reset 复杂度为 $O(C)$
  • 空间复杂度：$O(C)$

最后

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

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

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

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