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 <= 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.
Rust Solution
use rand::prelude::*;
use std::collections::HashMap;
struct Solution {
size: usize,
indexes: HashMap<usize, usize>,
rng: ThreadRng,
rows: usize,
cols: usize,
}
impl Solution {
fn new(n_rows: i32, n_cols: i32) -> Self {
let rows = n_rows as usize;
let cols = n_cols as usize;
let size = rows * cols;
let indexes = HashMap::new();
let rng = thread_rng();
Solution {
size,
indexes,
rng,
rows,
cols,
}
}
fn flip(&mut self) -> Vec<i32> {
let r = self.rng.gen_range(0, self.size);
let x = *self.indexes.entry(r).or_insert(r);
self.size -= 1;
let y = *self.indexes.entry(self.size).or_insert(self.size);
*self.indexes.entry(r).or_default() = y;
let col = x % self.cols;
let row = x / self.cols;
vec![row as i32, col as i32]
}
fn reset(&mut self) {
self.size = self.rows * self.cols;
self.indexes = HashMap::new();
}
}
Having problems with this solution? Click here to submit an issue on github.