题目链接：https://leetcode-cn.com/problems/random-flip-matrix/

解题思路：

由于数据量为 10000 * 10000，所以任何存储类型的解法都不行了。
在这里利用的一个降维的思路，把二维的坐标映射到一维上，不过这样还是不能AC。因为 朴素 的做法是：把所有的数据存储到一个容器中，然后用随机取这个容器的下标，然后再将容器中对应下标的数值删去，这样的空间复杂度不合格。所以，在这里提出了一种很巧妙的方式，我们不需要存储那么多数据。
首先，刚开始时所有元素都为0，如果想要把元素置为1，那么下标的选择为[0, toal），其中 total = m * n。我们随机选择一个下标 index，然后将下标 index 和 total - 1进行交换。（为什么要这么做？这样做就可以把所有值为0的元素下标放置到一起，组成一个连续的区间，我们只需要维护一个 total 变量就能做到取随机数的功能，而不是像朴素的做法，需要一个容器去存储。）

  1. class Solution {
  2.     int m, n, total;
  3.     Map<Integer, Integer> map = new HashMap<>();
  4.     Random rand = new Random();
  6.     public Solution(int m, int n) {
  7.         this.m = m;
  8.         this.n = n;
  9.         this.total = m * n;
  11.     }
  14.     public int[] flip() {
  15.         int i = rand.nextInt(total);
  16.         int k = map.getOrDefault(i, i); // 如果map中找不到则说明还没被访问过，返回初始化的值
  17.         int swap = map.getOrDefault(total-1, total-1); // arr[z-1]
  18.         // 交换
  19.         map.put(i, swap);
  20.         //map.put(total-1, k); //这句不加也没事，因为也取不到 total-1 的随机数
  21.         total--;
  22.         return new int[]{k/n, k%n};
  24.     }
  26.     public void reset() {
  27.         total = m * n;
  28.         map.clear();
  29.     }
  30. }
  32. /**
  33.  * Your Solution object will be instantiated and called as such:
  34.  * Solution obj = new Solution(m, n);
  35.  * int[] param_1 = obj.flip();
  36.  * obj.reset();
  37.  */