LeetCode 519. 随机翻转矩阵（哈希）数据结构与算法Michael是个半路程序员-

1. 题目

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

注意: 1 <= n_rows, n_cols <= 10000 0 <= row.id < n_rows 并且 0 <= col.id < n_cols 当矩阵中没有值为 0 时，不可以调用 flip 函数 调用 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 没有参数，参数总会以列表形式给出，哪怕该列表为空 

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/random-flip-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

类似题目：LeetCode 398. 随机数索引（概率）

2.1 超时解

• 矩阵很大的时候，翻得时候效率很低，会碰到翻过的，还要去重新翻

class Solution { //超时     vector<int> grid; int m, n; int x, y, pos; public: Solution(int n_rows, int n_cols) {         grid = vector<int> (n_rows*n_cols, 0);         m = n_rows;         n = n_cols; }          vector<int> flip() { do {             pos = rand()%(m*n); }while(grid[pos] == 1);         grid[pos] = 1; return {pos/n, pos-pos/n*n}; } void reset() {         grid = vector<int> (m*n, 0); } }; 

2.2 转一维，每次缩小范围

• 记录总共的元素个数N，随机获取 0 ~ N-1 的 pos
• 如果map中有key = pos，则 pos = map[pos]，如果没有，pos就是pos
• 还需要把当前取的位置的 map的 value 更新为最后一个位置的，下一轮，最后那个位置就跳过了
  

class Solution {     unordered_map<int,int> map; int m, n, num; int x, y, pos, prev; public: Solution(int n_rows, int n_cols) {         m = n_rows;         n = n_cols;         num = m*n; }          vector<int> flip() { if(num == 0) return {};         pos = rand()%(num);         num--;//下一轮，减少一个数 if(map.count(pos))//map包含pos的key {             prev = pos;//记录当前pos             pos = map[pos];//真实的取走的pos if(!map.count(num))//把最后一个位置的数换到当前                 map[prev] = num; else//如果最后一个位置有map值，用其值替换                 map[prev] = map[num]; } else//map不包含pos的key { //pos就是当前位置，只需把末尾的数替换到当前，同上 if(!map.count(num))                 map[pos] = num; else                 map[pos] = map[num]; }         x = pos/n;         y = pos-x*n; return {x, y}; } void reset() {         num = m*n;         map.clear(); } }; 

36 ms 18.6 MB