519. Random Flip Matrix 随机翻转矩阵

# 题目描述：

You are given the number of rows `n_rows` and number of columns `n_cols` of a 2D binary matrix where all values are initially 0. Write a function `flip` which chooses a 0 value uniformly at random, changes it to 1, and then returns the position `[row.id, col.id]` of that value. Also, write a function `reset` which sets all values back to 0. Try to minimize the number of calls to system's Math.random() and optimize the time and space complexity.

Note:

1. `1 <= n_rows, n_cols <= 10000`
2. `0 <= row.id < n_rows` and `0 <= col.id < n_cols`
3. `flip` will not be called when the matrix has no 0 values left.
4. the total number of calls to `flip` and `reset` will not exceed 1000.

Example 1:

``````Input:
["Solution","flip","flip","flip","flip"]
[[2,3],[],[],[],[]]
Output: [null,[0,1],[1,2],[1,0],[1,1]]
``````

Example 2:

``````Input:
["Solution","flip","flip","reset","flip"]
[[1,2],[],[],[],[]]
Output: [null,[0,0],[0,1],null,[0,0]]
``````

Explanation of Input Syntax:

The input is two lists: the subroutines called and their arguments. Solution's constructor has two arguments, n_rows and n_cols. flip and reset have no arguments. Arguments are always wrapped with a list, even if there aren't any.

# 解题方法

# 方法一：循环生成随机数

``````class Solution(object):

def __init__(self, n_rows, n_cols):
"""
:type n_rows: int
:type n_cols: int
"""
self.M = n_rows
self.N = n_cols
self.total = self.M * self.N
self.fliped = set()

def flip(self):
"""
:rtype: List[int]
"""
pos = random.randint(0, self.total - 1)
while pos in self.fliped:
pos = random.randint(0, self.total - 1)
return [pos / self.N, pos % self.N]

def reset(self):
"""
:rtype: void
"""
self.fliped.clear()

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

# 方法二：Fisher–Yates shuffle 洗牌算法

``````["Solution", "flip", "flip", "flip", "flip", "flip", "flip"]
[[2, 3], [], [], [], [], [], []]
``````

``````(0, 0, 5, {0: 5})
(0, 5, 4, {0: 4})
(3, 3, 3, {0: 4, 3: 3})
(2, 2, 2, {0: 4, 2: 2, 3: 3})
(1, 1, 1, {0: 4, 1: 1, 2: 2, 3: 3})
(0, 4, 0, {0: 4, 1: 1, 2: 2, 3: 3})
``````

``````class Solution(object):

def __init__(self, n_rows, n_cols):
"""
:type n_rows: int
:type n_cols: int
"""
self.M = n_rows
self.N = n_cols
self.total = self.M * self.N
self.d = dict()

def flip(self):
"""
:rtype: List[int]
"""
r = random.randint(0, self.total - 1)
self.total -= 1
x = self.d.get(r, r)
self.d[r] = self.d.get(self.total, self.total)
# print(r, x, self.total, self.d)
return [x / self.N, x % self.N]

def reset(self):
"""
:rtype: void
"""
self.d.clear()
self.total = self.M * self.N

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

# 日期

2018 年 10 月 19 日 —— 自古逢秋悲寂寥，我言秋日胜春朝