Today we will read on this article – Random flip matrix in C ++: If we have n_rows the number of rows and the number of columns of n_cols. All values here are initially 0. We have to define a function flip () that randomly selects the 0 value equally, changes it to 1, and then returns the position of that value to [row.id, col.id]. In addition, we need to write another function reset (), which sets all values to 0.. We need to reduce the number of calls to Math.random () of the system and try to optimize the complexity of time and space.
Example
#include <bits/stdc++.h> using namespace std; void print_vector(vector<int> v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << v[i] << ", "; } cout << "]"<<endl; } class Solution { public: unordered_map <int, int> holes; int n; int m; int size; program(int n_rows, int n_cols) { srand(time(NULL)); n = n_rows; m = n_cols; size = n * m; } vector<int> flip() { int id = rand() % size; size--; int rid = id; if(holes.count(id)){ id = holes[id]; } holes[rid] = holes.count(size) ? holes[size] : size; return {id / m, id % m}; } void reset() { size = n * m; holes.clear(); } }; main(){ Solution ob(2,2); print_vector(ob.flip()); print_vector(ob.flip()); print_vector(ob.flip()); print_vector(ob.flip()); }
Input
Initialize the constructor using 2,2 and call flip four times
Output
[1, 1, ] [0, 0, ] [1, 0, ] [0, 1, ]