LeetCode 题解工作台
随机翻转矩阵
给你一个 m x n 的二元矩阵 matrix ，且所有值被初始化为 0 。请你设计一个算法，随机选取一个满足 matrix[i][j] == 0 的下标 (i, j) ，并将它的值变为 1 。所有满足 matrix[i][j] == 0 的下标 (i, j) 被选取的概率应当均等。 尽量最少调用内…
4
题型
2
代码语言
3
相关题
当前训练重点
中等 · 哈希·数学
答案摘要
class Solution: def __init__(self, m: int, n: int):
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 哈希·数学 题型思路
题目描述
给你一个 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]，并将其对应格子中的值变为1void 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 <= 104- 每次调用
flip时，矩阵中至少存在一个值为 0 的格子。 - 最多调用
1000次flip和reset方法。
解题思路
方法一
class Solution:
def __init__(self, m: int, n: int):
self.m = m
self.n = n
self.total = m * n
self.mp = {}
def flip(self) -> List[int]:
self.total -= 1
x = random.randint(0, self.total)
idx = self.mp.get(x, x)
self.mp[x] = self.mp.get(self.total, self.total)
return [idx // self.n, idx % self.n]
def reset(self) -> None:
self.total = self.m * self.n
self.mp.clear()
# Your Solution object will be instantiated and called as such:
# obj = Solution(m, n)
# param_1 = obj.flip()
# obj.reset()
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Can the candidate explain the optimization trade-off between space and time complexity for this problem?
- question_mark
Does the candidate understand the importance of randomness in this problem and how reservoir sampling contributes to it?
- question_mark
Can the candidate implement an efficient reset method without unnecessary iterations over the entire matrix?
常见陷阱
外企场景- error
Failing to implement uniform randomness in the flip operation, leading to biased index selection.
- error
Using inefficient methods for resetting the matrix, causing excessive time complexity.
- error
Not properly managing the space complexity, leading to memory inefficiencies with large matrices.
进阶变体
外企场景- arrow_right_alt
What if we allow multiple flips of the same index? How would that affect the implementation?
- arrow_right_alt
Can this solution be adapted to handle a dynamic size matrix where m and n are continuously changing?
- arrow_right_alt
What if the flip function was to be called in a highly concurrent environment? How would you handle synchronization?