519 Random Flip Matrix

519. Random Flip Matrix

1. Question

You are given the number of rowsn_rows and number of columnsn_cols of a 2D binary matrix where all values are initially 0. Write a functionflip 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 functionresetwhich 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. 1 <= n_rows, n_cols <= 10000

2. 0 <= row.id < n_rowsand0 <= col.id < n_cols

3. flipwill not be called when the matrix has no 0 values left.

4. the total number of calls to flipandresetwill 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_rowsandn_cols. flip andresethave no arguments. Arguments are always wrapped with a list, even if there aren't any.

2. Implementation

(1) Fisher-Yate 算法

class Solution {
    // 思路: Fisher-Yate的2D版本
    Map<Integer, Integer> map;
    Random rand;
    int rows, cols, total;

    public Solution(int n_rows, int n_cols) {
        map = new HashMap();
        rand = new Random();
        rows = n_rows;
        cols = n_cols;
        total = rows * cols;
    }

    public int[] flip() {
        int index = rand.nextInt(total--);
        // Check if we have put anything in this index
        int x = map.getOrDefault(index, index);
        // swap index with total
        map.put(index, map.getOrDefault(total, total));
        return new int[] {x / cols, x % cols};
    }

    public void reset() {
        map.clear();
        total = rows * cols;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(n_rows, n_cols);
 * int[] param_1 = obj.flip();
 * obj.reset();
 */

3. Time & Space Complexity

Fisher-Yate 时间复杂度flip: O(1), 空间复杂度O(m * n), 空间主要是map，m为行，n为列