随机翻转矩阵

难度: Medium

给你一个 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 方法。

Submission

运行时间: 34 ms

内存: 16.6 MB

class Solution:
    def __init__(self, m: int, n: int):
        self.m, self.n = m, n
        self.total = m * n - 1
        self.record = dict()

    def flip(self) -> List[int]:
        r = random.randint(0, self.total)
        idx = self.record.get(r, r)
        # 相当于total的值没被用，将那个值填入idx位置；
        # 被用了的话，将它那里填入的没被用的值填入
        self.record[r] = self.record.get(self.total, self.total)
        self.total -= 1
        ans = [idx // self.n, idx % self.n]
        return ans

    def reset(self) -> None:
        self.total = self.m * self.n - 1
        self.record = dict()

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

Explain

这个解决方案使用了一个映射表（哈希表）来记录已被随机选取的索引。每当调用flip函数时，它将从未被选择的索引中随机选取一个。使用一个整数total来跟踪还没有被选择的索引数量。如果一个索引已经被选取，它会被哈希表中映射到一个新的未被选取的索引。这样可以避免使用一个完整的矩阵来存储状态，从而节省空间并优化性能。

时间复杂度: O(1)

空间复杂度: O(min(m*n, 1000))

class Solution:
    def __init__(self, m: int, n: int):
        self.m, self.n = m, n
        self.total = m * n - 1
        self.record = dict()

    def flip(self) -> List[int]:
        r = random.randint(0, self.total)  # 随机选择一个未被选过的索引
        idx = self.record.get(r, r)  # 获取实际应该返回的索引，如果没有被映射则返回自身
        # 更新映射表，将选中的索引映射到当前的最后一个索引，或已经映射的最后一个索引
        self.record[r] = self.record.get(self.total, self.total)
        self.total -= 1  # 减少可选的索引数量
        ans = [idx // self.n, idx % self.n]  # 计算行列位置
        return ans

    def reset(self) -> None:
        self.total = self.m * self.n - 1  # 重置可选索引数量
        self.record = dict()  # 清空映射表

Explore

在flip函数中，每次选择一个随机索引`r`时，都是从当前未被选中的索引范围`[0, self.total]`中随机选取的。由于每次选择后，`self.total`都会减少1，并且通过哈希表的映射机制确保任何已经被选择的索引都映射到一个未被选择的新索引上，这样每个索引在每次调用`flip`时被选中的机会都是均等的，保证了每个索引被选中的概率是相同的。

不会。映射方法的设计是为了确保每个索引被选中的概率保持一致。当一个索引`r`被选中后，通过映射将其指向另一个尚未被选中的索引（通常是当前的`self.total`索引）。这种映射确保了即使`r`已经被使用，后续选择时它仍指向一个有效的未使用索引。因此，每个索引被选中的次数在长期运行中将均等分布，不会因映射机制而有所偏差。

是的，reset函数将`self.total`重置为`m * n - 1`，并且清空了哈希表`self.record`。这确保了类的状态完全回到了初始状态，如同新创建一个实例一样，所有的索引都重新变为可选，并且没有任何映射记录。

`self.record.get(r, r)`表示尝试从哈希表`self.record`中获取键`r`的值，如果`r`不存在，则返回`r`自身。这确保了即使某个索引尚未映射，它也能正确返回自身作为结果。`self.record.get(self.total, self.total)`用于更新映射表，表示如果`self.total`已经有映射，则使用其映射值，否则使用`self.total`自身。这种方法在每次flip调用时，都将已选索引`r`映射到当前最末尾的索引`self.total`，保持映射的连续性和有效性，从而确保所有索引能均等地被随机选择。