来源: https://leetcode.com/problems/random-flip-matrix/discuss/154053

算法

记$n = nrows * ncols$，$\[0..n - 1\)$中的整数可以与二维坐标$\[0..nrows - 1\) \times \[0, ncols - 1\)$建立一一映射.考虑开这样一个数组vec

std::vector<int> vec(n);
std::iota(vec.begin(), vector.end());

也就是说，vec的初始值为

vec[i] = i;

然后将vec中的元素视为token/纸牌,每次flip随机从vec中选取一个一个元素作为被flip的值:

int select = rand() % vec.size();
int ret = vec[select];
return {ret / n_cols, ret % n_cols};

但是要把这个选取的vec[select]从数组中删除，因为数组中元素的顺序无所谓，我们可以采用交换到末尾，再pop_back()的方法:

int select = rand() % vec.size();
int ret = vec[select];
std::swap(vec[select], vec.back());
vec.pop_back();
return {ret / n_cols, ret % n_cols};

这样基本上可以在O(1)内flip,reset要重建数组需要O(n).
这里有一个循环不变量，vec中存放的永远是0..vec.size() - 1这些数的一个排列.
不过还有一个问题.
$nrows * ncols$的范围是$10000 * 10000$，而flip和reset调用的次数只有1000.如果我们

std::vector<int> vec(n_rows * n_cols);

空间会爆掉.
由于flip和reset调用的次数只有1000,也就是说vec中被调整了位置的元素大概只有1000个。为了利用这一点可以把vec用一个unordered_map[HTML_REMOVED]来表示:

std::unordered_map<int, int> map;

并且map中只存放vec[i] != i的{下标，值}对，基本上只需把所有使用vec[i]的地方换成map.getOrDefault(i, i);
完整的C++实现如下:

#include <random>
#include <unordered_map>
#include <vector>

class Solution {
  const int n_rows, n_cols;
  int n;
  std::unordered_map<int, int> map;

public:
  Solution(int n_rows, int n_cols) : n_rows(n_rows), n_cols(n_cols) { reset(); }

  std::vector<int> flip() {
    int v = rand() % n--;
    auto iter_n = map.find(n);
    int y = iter_n == map.end() ? n : iter_n->second;
    auto res = map.emplace(v, y);
    int x;
    if (res.second) {
      x = v;
    } else {
      x = res.first->second;
    }
    res.first->second = y;
    return {x / n_cols, x % n_cols};
  }

  void reset() {
    n = n_rows * n_cols;
    map.clear();
  }
};