力扣 519. 随机翻转矩阵_随机翻转矩阵 力扣

题目来源：https://leetcode-cn.com/problems/random-flip-matrix/

大致题意：
设计一个类，可以完成如下三个功能：

• 给定整数 m 和 n，初始化一个大小为 m * n 的矩阵
• 随机将矩阵中一个未翻转过的位置进行翻转，值设为 1
• 将矩阵重置为初始状态

思路

一开始我想使用一个集合存下所有未被翻转过的的坐标集合，然后翻转时在集合中随机抽取一个数，但是错了，也不知道咋错了。后面又发现这个法子根本行不通，这道题会卡空间复杂度为 O(mn)，也就是说申请一个大小为 mn 的数组在最后都会内存超限

只好去看题解，发现这道题的翻转次数在 10^3 以内，使用哈希表存下已经翻转过的位置，就可以减少复杂度

哈希表

为了方便计算，首先将二维矩阵坐标转换为一维 [i, j] ~ i * n + j

因为哈希表是按照哈希函数计算结果进行索引的，为了保证每个坐标被选中的概率相等，需要做一些处理：

• 假设有 mn 个坐标，目前已经翻转过 k 次，那么还有 mn - k 个位置未被翻转，为了使用 Random 类的 nextInt 方法，我们需要保证前 mn - k 个位置都未翻转，后 k 个位置被翻转
• 于是在 [0, mn - k) 之间随机出本次翻转的坐标 x 后，我们都将当前的最后一个坐标 mn - k - 1 与被选中的坐标 x 进行替换，具体的操作就是将被选中的坐标放入哈希表，键为当前坐标 x，值为区间的最后一个坐标 mn - k - 1
• 即对于本轮被选中的坐标，先查看哈希表中是否已经存在该坐标，若存在，代表当前坐标已经被翻转过，取出哈希表对应的值，将值对应坐标翻转；若不存在，直接放入哈希表即可。最后更新哈希表键值对，键为当前坐标 x，值为区间的最后一个坐标 mn - k - 1

代码：

public class Solution {
    Map<Integer, Integer> matrix = new HashMap<Integer, Integer>();
    int m;
    int n;
    int total;
    public Solution(int m, int n) {
        total = m * n;
        this.n = n;
        this.m = m;
    }

    public int[] flip() {
        Random random = new Random();
        // 在 total 个待翻转的坐标中选择一个
        int rd = random.nextInt(total--);
        // 如果之前该坐标已经被选中过，那么选中其对应的值（也就是替换后的坐标）
        int idx = matrix.getOrDefault(rd, rd);
        // 放入哈希表 / 更新被选中坐标的替换坐标 为随机数区间的末尾坐标
        matrix.put(rd, matrix.getOrDefault(total, total));
        // 转换为二维坐标
        return new int[]{idx / n, idx % n};
    }

    public void reset() {
        matrix.clear();
        total = m * n;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28