题目要求
给你一个 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] 的概率应当相同
题解
一、暴力遍历+deepcopy
import copy class Solution1(): def __init__(self, m, n): self.matrix = [] for i in range(0, m): self.matrix.append([]) for j in range(0, n): self.matrix[i].append(0) self.ba = copy.deepcopy(self.matrix) def flip(self): m = len(self.matrix) n = len(self.matrix[0]) a = random.randrange(0, m) b = random.randrange(0, n) while(self.matrix[a][b] != 0): a = random.randrange(0, m) b = random.randrange(0, n) self.matrix[a][b] = 1 return [a, b] def reset(self): self.matrix = self.ba return self.ba
大部分人都能想到的方法，但是会超时，本题没必要新建一个题目所要求的二维数组，只需要将0和1对应的下标记录下来，再对下标进行相应的处理即可。以下给出另外两种解法。
二、set集合
class Solution: def __init__(self, n_rows: int, n_cols: int): self.s = set() self.n = n_rows self.m = n_cols def flip(self) -> List[int]: while True: x = (random.randint(0, self.n - 1), random.randint(0, self.m - 1)) if x not in self.s: self.s.add(x) return [x[0], x[1]] def reset(self) -> None: self.s.clear()
三、哈希映射
class Solution: def __init__(self, m: int, n: int): self.m = m self.n = n self.total = m * n self.map = {} def flip(self) -> List[int]: x = random.randint(0, self.total - 1) self.total -= 1 # 查找位置 x 对应的映射 idx = self.map.get(x, x) # 将位置 x 对应的映射设置为位置 total 对应的映射 self.map[x] = self.map.get(self.total, self.total) return [idx // self.n, idx % self.n] def reset(self) -> None: self.total = self.m * self.n return self.map.clear()
