# leetcode519. Random Flip Matrix

## 题目要求

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. 1 <= n_rows, n_cols <= 10000
2. 0 <= row.id < n_rows and 0 <= col.id < n_cols
3. flip will not be called when the matrix has no 0 values left.
4. 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.

## 思路和代码

```    Map<Integer, Integer> map;
Random                r;
int rowCount;
int columnCount;
int flipCount;
public Solution(int n_rows, int n_cols) {
map = new HashMap<>();
r = new Random();
rowCount = n_rows;
columnCount = n_cols;
flipCount = rowCount * columnCount;
}

public int[] flip() {
int randomIndex = r.nextInt(flipCount--);
int value = map.getOrDefault(randomIndex, randomIndex);
map.put(randomIndex, map.getOrDefault(flipCount, flipCount));
return new int[]{value/columnCount, value%columnCount};
}

public void reset() {
map.clear();
flipCount = rowCount * columnCount;
}```

0 条评论

• ### leetcode375. Guess Number Higher or Lower II

一个猜数字游戏，数字区间为1~n，每猜一次，会有人告诉你猜中了或者当前的数字是大于结果值还是小于结果值。猜对则本次猜测免费，猜错则本次猜测需要花费和数字等额的金...

• ### leetcode495. Teemo Attacking

In LOL world, there is a hero called Teemo and his attacking can make his enemy ...

• ### leetcode452. Minimum Number of Arrows to Burst Balloons

There are a number of spherical balloons spread in two-dimensional space. For ea...

• ### π框架之实战项目（代码分享）

通过之前的学习，本文主要介绍一下实现用户的登录、注册等功能的接口代码，让大家通过小实战来感悟phalapi框架的神奇之处。（以下代码均可右滑） ? 获取参数规则...

• ### OCP-052考试题库汇总（9）-CUUG内部解答版

Which three are true about Optimizer Statistics?

• ### HDU 1728 逃离迷宫(DFS经典题，比赛手残写废题)

逃离迷宫 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java...

• ### 771. Jewels and Stones

思路： 记录J的信息，遍历S，采用Hashmap的思路，每次查询O(1)，总时间复杂度为O(n)

• ### idea 项目名称红色 解决办法

idea如果当前project用了版本控制器，其下面新建的所有的项目默认都是加入到版本控制里面，所以项目名称和文件都是红色的；

• ### 线上出bug了？别怕，这么定位！

工作中，生产环境代码是编译后代码，搜集到报错信息的行和列无法在源码中对应，很多时候只能靠“经验”去猜，本文针对这种情况，开发了一个npm命令行小工具，帮助快速定...