LeetCode 519. 随机翻转矩阵（哈希）

注意:
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 没有参数，参数总会以列表形式给出，哪怕该列表为空

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);
    }
};

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();
    }
};