Problem
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
Ā andĀ0 <= col.id < n_cols
flip
Ā will not be called when the matrix has noĀ 0 values left.- 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.
Solution 1: Hashtable + Resample
Time complexity: O(|flip|) = O(1000) = O(1)
Space complexity: O(|flip|) =Ā O(1000) = O(1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
// Author: Huahua // Running time: 12 ms class Solution { public: Solution(int n_rows, int n_cols): rows_(n_rows), cols_(n_cols), n_(rows_ * cols_) {} vector<int> flip() { int index = rand() % n_; while (m_.count(index)) index = rand() % n_; m_.insert(index); return {index / cols_, index % cols_}; } void reset() { m_.clear(); n_ = rows_ * cols_; } private: const int rows_; const int cols_; int n_; unordered_set<int> m_; }; |
Solution 2:Ā FisherāYates shuffle
Generate a random shuffle of 0 to n – 1, one number at a time.
Time complexity: flip: O(1)
Space complexity: O(|flip|) = O(1000) = O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
// Author: Huahua // Running time: 12 ms class Solution { public: Solution(int n_rows, int n_cols): rows_(n_rows), cols_(n_cols), n_(rows_ * cols_) {} vector<int> flip() { int s = rand() % (n_--); int index = s; if (m_.count(s)) index = m_[s]; m_[s] = m_.count(n_) ? m_[n_] : n_; return {index / cols_, index % cols_}; } void reset() { m_.clear(); n_ = rows_ * cols_; } private: const int rows_; const int cols_; int n_; unordered_map<int, int> m_; }; |