There is an m x n binary grid matrix with all the values set 0 initially. Design an algorithm to randomly pick an index (i, j) where matrix[i][j] == 0 and flips it to 1. All the indices (i, j) where matrix[i][j] == 0 should be equally likely to be returned.
Optimize your algorithm to minimize the number of calls made to the built-in random function of your language and optimize the time and space complexity.
Implement the Solution class:
Solution(int m, int n)Initializes the object with the size of the binary matrix m and n.int[] flip()Returns a random index[i, j]of the matrix wherematrix[i][j] == 0and flips it to 1.void reset()Resets all the values of the matrix to be 0.
点击查看代码
class Solution:
def __init__(self, m: int, n: int):
self.row = m
self.col = n
self.start = 0
self.end = m * n
self.pos_map = {}
def flip(self) -> List[int]:
idx = random.randrange(self.start, self.end)
res = self.pos_map.get(idx, idx)
self.pos_map[idx] = self.pos_map.get(self.start, self.start)
self.start += 1
return (res // self.col, res % self.col)
def reset(self) -> None:
self.start = 0
self.pos_map = {}
# Your Solution object will be instantiated and called as such:
# obj = Solution(m, n)
# param_1 = obj.flip()
# obj.reset()