519-随机翻转矩阵(Random Flip Matrix)

原文链接: https://leetcode-cn.com/problems/random-flip-matrix

英文原文

There is an m x n binary grid matrix with all the values set 0 initially. Design an algorithm to randomly pick an index (i, j) where matrix[i][j] == 0 and flips it to 1. All the indices (i, j) where matrix[i][j] == 0 should be equally likely to be returned.

Optimize your algorithm to minimize the number of calls made to the built-in random function of your language and optimize the time and space complexity.

Implement the Solution class:

Solution(int m, int n) Initializes the object with the size of the binary matrix m and n.
int[] flip() Returns a random index [i, j] of the matrix where matrix[i][j] == 0 and flips it to 1.
void reset() Resets all the values of the matrix to be 0.

Example 1:

Input
["Solution", "flip", "flip", "flip", "reset", "flip"]
[[3, 1], [], [], [], [], []]
Output
[null, [1, 0], [2, 0], [0, 0], null, [2, 0]]

Explanation
Solution solution = new Solution(3, 1);
solution.flip();  // return [1, 0], [0,0], [1,0], and [2,0] should be equally likely to be returned.
solution.flip();  // return [2, 0], Since [1,0] was returned, [2,0] and [0,0]
solution.flip();  // return [0, 0], Based on the previously returned indices, only [0,0] can be returned.
solution.reset(); // All the values are reset to 0 and can be returned.
solution.flip();  // return [2, 0], [0,0], [1,0], and [2,0] should be equally likely to be returned.

Constraints:

1 <= m, n <= 10⁴
There will be at least one free cell for each call to flip.
At most 1000 calls will be made to flip and reset.

中文题目

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

通过代码

高赞题解

双指针

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

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

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

代码：

[]
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$ 的映射值，同时维护了随机区间的连续性。

代码：

[]
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)$

最后

今天是连续更新每日一题题解的第 $300$ 天 🎉 🎉

前天感恩节的时候收到了很多同学的感谢留言，其实是我更应该感谢大家，没有你们或许我不会坚持这么久。是你们每天的反馈与陪伴，强化了我认为做这事很有意义的想法。

特殊的日子，开个赞赏拍个全家福，仍然是「学生免费，非学生是否赞赏都能看」的原则。

另外需要强调：力扣「赞赏」行为的发生，必须基于「你十分喜欢该作者」&「你十分喜欢该平台」，两者缺一不可。

如果你确定满足上述所有条件的话，可以花 最多一元（千万千万不要给多了，就给一元就行） 留个头像 🤣，或者只需给我点个赞留个言，我也同样开心 ❤️

看起来 LeetCode 的赞赏功能出现问题了（本界面和赞赏明细，我都看不到大家的记录，钱应该是被卡在中间了 🤣）。大家不要赞赏了，大家不要赞赏了，大家不要赞赏了！！！ 🤣
但为了前面打赏的同学之后能够正常显示，因此还是保持赞赏的打开状态。
如果可以，希望 @LeetCode 可以回退掉这些赞赏给用户，并给予这些用户一定的积分补偿。

统计信息

通过次数	提交次数	AC比率
19214	40827	47.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途