{"id":3398,"date":"2018-07-31T08:33:05","date_gmt":"2018-07-31T15:33:05","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=3398"},"modified":"2018-07-31T08:36:28","modified_gmt":"2018-07-31T15:36:28","slug":"leetcode-881-random-flip-matrix","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-881-random-flip-matrix\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 881. Random Flip Matrix"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

You are given the number of rows\u00a0n_rows<\/code>\u00a0and number of columns\u00a0n_cols<\/code>\u00a0of a\u00a02D\u00a0binary matrix\u00a0where all values are initially 0.\u00a0Write a function\u00a0flip<\/code>\u00a0which chooses\u00a0a 0 value\u00a0uniformly at random<\/a>,\u00a0changes it to 1,\u00a0and then returns the position\u00a0[row.id, col.id]<\/code>\u00a0of that value. Also, write a function\u00a0reset<\/code>\u00a0which sets all values back to 0.\u00a0Try to minimize the number of calls to system’s Math.random()<\/strong>\u00a0and optimize the time and\u00a0space complexity.<\/p>\n

Note:<\/p>\n

    \n
  1. 1 <= n_rows, n_cols\u00a0<= 10000<\/code><\/li>\n
  2. 0 <= row.id < n_rows<\/code>\u00a0and\u00a00 <= col.id < n_cols<\/code><\/li>\n
  3. flip<\/code>\u00a0will not be called when the matrix has no\u00a00 values left.<\/li>\n
  4. the total number of calls to\u00a0flip<\/code>\u00a0and\u00a0reset<\/code>\u00a0will not exceed\u00a01000.<\/li>\n<\/ol>\n

    Example 1:<\/strong><\/p>\n

    Input: \r\n<\/strong>[\"Solution\",\"flip\",\"flip\",\"flip\",\"flip\"]\r\n<\/span>[[2,3],[],[],[],[]]<\/span>\r\nOutput: <\/strong>[null,[0,1],[1,2],[1,0],[1,1]]<\/span>\r\n<\/pre>\n
    \n
    Example 2:<\/strong><\/p>\n
    Input: \r\n<\/strong>[\"Solution\",\"flip\",\"flip\",\"reset\",\"flip\"]\r\n<\/span>[[1,2],[],[],[],[]]<\/span>\r\nOutput: <\/strong>[null,[0,0],[0,1],null,[0,0]]<\/span><\/pre>\n<\/div>\n
    Explanation of Input Syntax:<\/strong><\/p>\n
    The input is two lists:\u00a0the subroutines called\u00a0and their\u00a0arguments.\u00a0Solution<\/code>‘s constructor\u00a0has two arguments,\u00a0n_rows<\/code>\u00a0and\u00a0n_cols<\/code>.\u00a0flip<\/code>\u00a0and\u00a0reset<\/code>\u00a0have\u00a0no\u00a0arguments.\u00a0Arguments\u00a0are\u00a0always wrapped with a list, even if there aren’t any.<\/p>\n
    Solution 1: Hashtable + Resample<\/strong><\/h1>\n
    Time complexity: O(|flip|) = O(1000) = O(1)<\/p>\n
    Space complexity: O(|flip|) =\u00a0O(1000) = O(1)<\/p>\n
    \/\/ Author: Huahua\r\n\/\/ Running time: 12 ms\r\nclass Solution {\r\npublic:\r\n  Solution(int n_rows, int n_cols): \r\n    rows_(n_rows), cols_(n_cols), n_(rows_ * cols_) {}\r\n\r\n  vector<int> flip() {\r\n    int index = rand() % n_;\r\n    while (m_.count(index))\r\n      index = rand() % n_;    \r\n    m_.insert(index);\r\n    return {index \/ cols_, index % cols_};\r\n  }\r\n\r\n  void reset() {\r\n    m_.clear();\r\n    n_ = rows_ * cols_;\r\n  }\r\nprivate:\r\n  const int rows_;\r\n  const int cols_;\r\n  int n_;\r\n  unordered_set<int> m_;\r\n};<\/pre>\n
    Solution 2:\u00a0<\/strong>Fisher\u2013Yates shuffle<\/a><\/h1>\n
    Generate a random shuffle of 0 to n – 1, one number at a time.<\/p>\n
    Time complexity: flip: O(1)<\/p>\n
    Space complexity: O(|flip|) = O(1000) = O(1)<\/p>\n
    C++<\/p>\n
    \/\/ Author: Huahua\r\n\/\/ Running time: 12 ms\r\nclass Solution {\r\npublic:\r\n  Solution(int n_rows, int n_cols): \r\n    rows_(n_rows), cols_(n_cols), n_(rows_ * cols_) {}\r\n\r\n  vector<int> flip() {\r\n    int s = rand() % (n_--);\r\n    int index = s;\r\n    if (m_.count(s))\r\n      index = m_[s];\r\n    m_[s] = m_.count(n_) ? m_[n_] : n_;\r\n    return {index \/ cols_, index % cols_};\r\n  }\r\n\r\n  void reset() {\r\n    m_.clear();\r\n    n_ = rows_ * cols_;\r\n  }\r\nprivate:\r\n  const int rows_;\r\n  const int cols_;\r\n  int n_;\r\n  unordered_map<int, int> m_;\r\n};<\/pre>\n
     <\/p>\n","protected":false},"excerpt":{"rendered":"
    Problem You are given the number of rows\u00a0n_rows\u00a0and number of columns\u00a0n_cols\u00a0of a\u00a02D\u00a0binary matrix\u00a0where all values are initially 0.\u00a0Write a function\u00a0flip\u00a0which chooses\u00a0a 0 value\u00a0uniformly at random,\u00a0changes…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184],"tags":[177,91,258,256],"class_list":["post-3398","post","type-post","status-publish","format-standard","hentry","category-array","tag-medium","tag-random","tag-sample","tag-shuffle","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3398","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=3398"}],"version-history":[{"count":5,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3398\/revisions"}],"predecessor-version":[{"id":3403,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3398\/revisions\/3403"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3398"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3398"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3398"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}