1.题目基本信息

1.1.题目描述

给你一个 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.题目地址

https://leetcode.cn/problems/random-flip-matrix/description/

2.解题方法

2.1.解题思路

一维化+哈希表。假设剩余cnt个位置没有取，则维护一个[1,cnt]的区间，在这个连续的区间中的随机的取数，对于取到的随机数index，如果index<cnt，为了还可以用index，可以将index映射到一个没有取的位置，由于去除一个后cnt缩小，所以可以将index映射到cnt处，如果cnt也已经被取，则将index映射到cnt的映射值上

3.解题代码

python3代码

class Solution:
    # 思路：一维化+哈希表。假设剩余cnt个位置没有取，则维护一个[1,cnt]的区间，在这个连续的区间中的随机的取数，对于取到的随机数index，如果index<cnt，为了还可以用index，可以将index映射到一个没有取的位置，由于去除一个后cnt缩小，所以可以将index映射到cnt处，如果cnt也已经被取，则将index映射到cnt的映射值上
    def __init__(self, m: int, n: int):
        self.m = m
        self.n = n
        self.cnt = m * n    # 维护剩下能取的位置数
        self.map = {}       # 维护连续区间index->「cnt外的空闲块」的映射

    def flip(self) -> List[int]:
        # 这里的下标从1开始
        index = random.randint(1, self.cnt)
        value = self.map.get(index, index)
        self.map[index] = self.map.get(self.cnt, self.cnt)
        self.cnt -= 1
        return [(value - 1) // self.n, (value - 1) % self.n]

    def reset(self) -> None:
        self.map = {}
        self.cnt = self.m * self.n



# Your Solution object will be instantiated and called as such:
# obj = Solution(m, n)
# param_1 = obj.flip()
# obj.reset()

4.执行结果