Random Flip Matrix 随机翻转矩阵

题中给出一个 n 行 n 列的二维矩阵 (n_rows,n_cols)，且所有值被初始化为 0。要求编写一个 flip 函数，均匀随机的将矩阵中的 0 变为 1，并返回该值的位置下标 [row_id,col_id]；同样编写一个 reset 函数，将所有的值都重新置为 0。尽量最少调用随机函数 Math.random()，并且优化时间和空间复杂度。

注意:

1.1 <= n_rows, n_cols <= 10000

2. 0 <= row.id < n_rows 并且 0 <= col.id < n_cols

3.当矩阵中没有值为 0 时，不可以调用 flip 函数

4.调用 flip 和 reset 函数的次数加起来不会超过 1000 次

示例 1：

输入: 
["Solution","flip","flip","flip","flip"]
[[2,3],[],[],[],[]]
输出: [null,[0,1],[1,2],[1,0],[1,1]]

示例 2：

输入: 
["Solution","flip","flip","reset","flip"]
[[1,2],[],[],[],[]]
输出: [null,[0,0],[0,1],null,[0,0]]

输入语法解释：

输入包含两个列表：被调用的子程序和他们的参数。Solution 的构造函数有两个参数，分别为 n_rows 和 n_cols。flip 和 reset 没有参数，参数总会以列表形式给出，哪怕该列表为空

思路：这道题需要用到Fisher–Yates 洗牌法，点击这里：Examples，重点是怎么用代码实现，discuss里面的代码确实不容易看懂，看了很久才明白：

我们需要维护一个map（key对应剩余牌中的下标，如果只剩下0,1,2,4,5这5张牌，下标依然是0,1,2,3,4。其次value对应已经置换的牌中key置换的尾牌的值），这里举一个例子：

比如初始牌为：0,1,2,3,4,5,6,7

选择了下标4的牌，那么map[4]=7，因为4的牌被置换出去，下次不参与洗牌，4的位置由7代替。

所以算法步骤为：

1：先初始化total=row*col

2：随机计算在[0,total)范围内的一个数值，记为r，这里r就是下标，比如只剩0,1,2,4,5这5张牌，那么选择下标3（r=3）对应的牌为4，显然r不是想要的值，理论上对应的牌应该为3，和下标保持一致，所以这里就需要map出场。并且total–

3：通过map[r]来得到真正的数值x，x才是真正牌的数值，这里为4。

4：然后我们需要把这张牌和尾牌置换，即更新map[r]的值，注意这里尾牌可能在之前的操作被其他牌置换了，所以尾牌的数值不一定等于total，所以要拿到total也要通过map[total]来取（真绕啊！！！）。

然后一直循环，直到total等于0。

这里为了方便理解，可以举如下例子，自己debug就知道了：

牌：0,1,2,3,4,5,6,7

第一轮：r=5

第二轮：r=0

第三轮：r=4

参考代码：

class Solution {
public:
	Solution(int n_rows, int n_cols) {
		total = n_rows * n_cols;
		row = n_rows;
		col = n_cols;
	}

	vector<int> flip() {
		int r = rand() % (total--);
		int x = (m.find(r) != m.end() ? m[r] : r);
		m[r] = (m.find(total)!=m.end()?m[total]:total);
		return {x/col,x%col};
	}

	void reset() {
		m.clear();
		total= row * col;
	}
private:
	unordered_map<int, int> m;
	int total;
	int row, col;
};

今天的文章Random Flip Matrix 随机翻转矩阵分享到此就结束了，感谢您的阅读。