0519. Random Flip Matrix
========================
题目信息
--------
:题号: 0519
:难度: Medium
:主题: 状态设计、随机抽样、矩阵翻转、重置
:原题: `LeetCode 0519 `_
:重点: flip 只能选择当前为 0 的格子、所有剩余零格等概率、选中后改为 1、reset 恢复全部零并共享对象状态
题目重述
--------
实现一个管理 ``m × n`` 二进制矩阵的对象,矩阵初始全部为 ``0``。``flip()`` 必须从当前仍为 ``0`` 的格子中等概率随机选择一个,返回其坐标 ``[row, col]``,并把该格子改为 ``1``。
在一次 ``reset()`` 之前,同一格子不能被 ``flip()`` 重复返回。``reset()`` 把所有格子重新设为 ``0``,之后每个格子又可以被选择。题目保证调用 ``flip()`` 时至少还存在一个零格;对象需要在多次调用之间保存矩阵状态。
自建示例
--------
两格矩阵不会重复翻转:
.. code-block:: text
输入:初始化 Solution(1,2),连续调用 flip() 两次
输出:第一次可能为 [0,0] 或 [0,1],第二次必须为另一个坐标
解释:第一次调用时两个零格各有 1/2 概率;被选格子变为 1 后,第二次只剩一个可选格子。
重置恢复可选状态:
.. code-block:: text
输入:初始化 Solution(1,1),调用 flip()、reset()、flip()
输出:[0,0],随后 [0,0]
解释:reset 后唯一格子恢复为 0,因此可以再次被翻转。
把未选择位置压缩成尾部交换表
------------------------------
把矩阵按行优先编号为 ``0..m*n-1``,维护尚未翻转的编号区间 ``[0, remaining)``。每次在区间内均匀抽取一个位置 ``pick``,将它映射到的真实编号返回;随后用区间最后一个位置替换 ``pick`` 的槽位并减少 ``remaining``。这样不需要显式保存整张矩阵。
哈希表只记录发生过交换的编号,未记录的位置默认映射到自身。``reset`` 清空映射并恢复 ``remaining = m*n``。
C++ 实现
--------
.. code-block:: cpp
class Solution {
int columns;
int total;
int remaining;
std::unordered_map mapping;
std::mt19937 generator{std::random_device{}()};
int actual(int index) {
auto it = mapping.find(index);
return it == mapping.end() ? index : it->second;
}
public:
Solution(int m, int n)
: columns(n), total(m * n), remaining(total) {}
std::vector flip() {
std::uniform_int_distribution distribution(0, remaining - 1);
int pick = distribution(generator);
int value = actual(pick);
int last = remaining - 1;
mapping[pick] = actual(last);
--remaining;
return {value / columns, value % columns};
}
void reset() {
mapping.clear();
remaining = total;
}
};
代码分析
--------
额外保存的 ``total`` 使 ``reset`` 能恢复原始矩阵大小;交换表的不变量是未翻转编号始终均匀占据前缀区间,因而每个剩余格子等概率。哈希查找使单次操作平均 ``O(1)``,空间复杂度为已翻转次数 ``O(t)``。