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
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.
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_; }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment