Formatted question description: https://leetcode.ca/all/519.html
519. Random Flip Matrix (Medium)
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 <= n_rows, n_cols <= 10000
0 <= row.id < n_rows
and0 <= col.id < n_cols
flip
will not be called when the matrix has no 0 values left.- the total number of calls to
flip
andreset
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.
Companies:
Google
Related Topics:
Random
Solution 1.
// OJ: https://leetcode.com/problems/random-flip-matrix/
// Time:
// Solution: O(MN)
// flip: O(1)
// reset: O(1)
// Space: O(MN)
class Solution {
private:
vector<int> v;
int size, M, N;
public:
Solution(int M, int N): M(M), N(N), size(M * N), v(M * N) {
for (int i = 0; i < size; ++i) v[i] = i;
srand(time(NULL));
}
vector<int> flip() {
swap(v[rand() % size], v[size - 1]);
--size;
return { v[size] / N, v[size] % N };
}
void reset() {
size = M * N;
}
};
Solution 2.
Same idea as Solution 1, but use unordered_map
to save space, and time if we only flip a small set of the points.
// OJ: https://leetcode.com/problems/random-flip-matrix/
// Time:
// Solution: O(1)
// flip: O(1)
// reset: O(MN) in worst case
// Space: O(MN) in worst case
// Ref: https://leetcode.com/problems/random-flip-matrix/solution/
class Solution {
private:
unordered_map<int, int> m;
int size, M, N;
//c++11 random integer generation
mt19937 rng{random_device{}()};
//uniform random integer in [0, bound]
int randint(int bound) {
uniform_int_distribution<int> uni(0, bound);
return uni(rng);
}
public:
Solution(int M, int N): M(M), N(N), size(M * N) {}
vector<int> flip() {
int r = randint(--size);
int x = m.count(r) ? m[r] : r;
m[r] = m.count(size) ? m[size] : size;
return { x / N, x % N };
}
void reset() {
m.clear();
size = M * N;
}
};
Java
-
```java class Solution { int n_rows; int n_cols; int remaining; Map<Integer, Integer> map; Random random;
public Solution(int n_rows, int n_cols) { this.n_rows = n_rows; this.n_cols = n_cols; remaining = n_rows * n_cols; map = new HashMap<Integer, Integer>(); random = new Random(); } public int[] flip() { int randNum = random.nextInt(remaining); remaining--; int index = map.getOrDefault(randNum, randNum); int value = map.getOrDefault(remaining, remaining); map.put(randNum, value); int[] rowColumn = {index / n_cols, index % n_cols}; return rowColumn; } public void reset() { map.clear(); remaining = n_rows * n_cols; } }
/**
- Your Solution object will be instantiated and called as such:
- Solution obj = new Solution(n_rows, n_cols);
- int[] param_1 = obj.flip();
- obj.reset(); */```
-
// OJ: https://leetcode.com/problems/random-flip-matrix/ // Time: // Solution: O(MN) // flip: O(1) // reset: O(1) // Space: O(MN) class Solution { private: vector<int> v; int size, M, N; public: Solution(int M, int N): M(M), N(N), size(M * N), v(M * N) { for (int i = 0; i < size; ++i) v[i] = i; srand(time(NULL)); } vector<int> flip() { swap(v[rand() % size], v[size - 1]); --size; return { v[size] / N, v[size] % N }; } void reset() { size = M * N; } };
-
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) self.fliped.add(pos) 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()