Because n_rows and n_COLs are up to 10^4, you can’t open a two-dimensional array because then the space complexity goes back to 10^8.
The number of calls to flip and reset will not be more than 1,000, so the matrix is sparse, and we just need to record the positions of all 1s. We can use a hash table to keep track of all the 1’s. For convenience, we map the two-dimensional position to an int variable, which is only recorded in the hash table. For example, if the position is row R and column C, then we get pos = r * cols + c, Where COLs is the number of columns of a two-dimensional matrix (i.e. N_cols), pos is the subscript that maps {r, c} to a one-dimensional space.
Pos = rand() % capacity (where capacity is the size of the matrix, n_rows * n_cols) And find the row number of the two-dimensional matrix corresponding to this position: r = pos/cols, column number: c = pos % cols, {r, c} as the return value of filp().
The reset() method simply clears the hash table to indicate that no position in the matrix is currently recorded with a value of 1.
The code is as follows:
using LL = long long; class Solution { public: unordered_set<LL> hash; // Hash table, record the position of the matrix map to the one-dimensional subscript LL Rows, cols, capacity; Solution(int n_rows, int n_cols) {rows = n_rows; cols = n_cols; capacity = rows * cols; } vector<int> flip() { LL r, c, pos; do { pos = rand() % capacity; // randomly get pos} while(hash.count(pos)! = 0); hash.insert(pos); r = pos / cols; Pos % cols = pos % cols; Return {(int)r, (int)c}; pos % cols return {(int)r, (int)c}; } void reset() { hash.clear(); // Empty the hash table}}; /** * Your Solution object will be instantiated and called as such: * Solution* obj = new Solution(n_rows, n_cols); * vector<int> param_1 = obj->flip(); * obj->reset(); * /Copy the code