# 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 {
public:
Solution(int n_rows, int n_cols) {
row = n_rows; col = n_cols;
}

vector<int> flip() {
while (true) {
int x = rand() % row, y = rand() % col;
if (!flipped.count(x * col + y)) {
flipped.insert(x * col + y);
return {x, y};
}
}
}

void reset() {
flipped.clear();
}

private:
int row, col;
unordered_set<int> flipped;
};
``````

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

vector<int> flip() {
while (true) {
int val = rand() % (row * col);
if (!flipped.count(val)) {
flipped.insert(val);
return {val / col, val % col};
}
}
}

void reset() {
flipped.clear();
}

private:
int row, col;
unordered_set<int> flipped;
};
``````

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

vector<int> flip() {
int id = rand() % size, val = id;
--size;
if (m.count(id)) id = m[id];
m[val] = m.count(size) ? m[size] : size;
return {id / col, id % col};
}

void reset() {
m.clear();
size = row * col;
}

private:
int row, col, size;
unordered_map<int, int> m;
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/519

https://leetcode.com/problems/random-flip-matrix/

https://leetcode.com/problems/random-flip-matrix/discuss/177809/c%2B%2B-solution

https://leetcode.com/problems/random-flip-matrix/discuss/154053/Java-AC-Solution-call-Least-times-of-Random.nextInt()-function

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation