教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载本篇技术指南以 LeetCode 519. 随机翻转矩阵 的题解为主体完整拆解「等概率随机选取矩阵中未被翻转的格子」这一经典无放回抽样问题。读者将掌握如何利用坐标编号把二维矩阵压缩为一维区间、如何在翻转操作导致区间断裂后仍保持单次随机与等概率以及「双指针扫描」与「哈希表 swap 映射」两种解法的原理、代码与复杂度边界并顺带理解其与 380、710 等同源题的通用套路。题目描述与核心难点给定一个m x n的二元矩阵matrix所有值初始化为0。需要实现一个Solution类支持Solution(int m, int n)按矩阵大小m、n初始化对象int[] flip()等概率随机返回一个满足matrix[i][j] 0的下标[i, j]并将其值变为1void reset()将矩阵中所有值重置为0。题目的附加要求是尽量最少调用内置随机函数并优化时间与空间复杂度。数据约束为1 m, n 10^4flip与reset最多被调用1000次且每次调用flip时矩阵中至少存在一个0。本题目有三个关键难点矩阵规模过大m, n最大可达10^4矩阵最多有10^8个格子无法真实构建二维数组也无法用标记数组记录每个格子是否被翻转过。无放回等概率每次flip都相当于从剩余为0的格子中做一次无放回随机抽取必须保证每个剩余格子被选中的概率均等。随机调用次数要少拒绝采样随机到一个已经被翻转的位置就重新随机在翻转次数接近总格子数时会被大量拒绝随机调用次数无法保证。核心思路二维坐标压缩为一维编号一个关键观察是二维坐标(i, j)与编号存在一一对应关系idx row * n col反过来给定编号idx可以还原出坐标row idx / n col idx % n这样一来问题就从「在m x n的二维矩阵中随机选未翻转格子」等价转换为「在[0, m * n)的一维区间中随机选一个未被使用的编号」。这正是整个题解的出发点二维问题的维度压缩。下文两种解法都在这个一维编号体系上展开。解法一双指针向两侧扫描借用「双指针」思想原始文档将该解法标记为「双指针」其思路是利用翻转总次数只有1000次数据范围10^3在[0, m * n)范围内随机出一个下标idx然后用两个指针分别从idx向左a和向右b扫描找到最近一个未被使用的位置将其标记翻转并返回。该做法相比「拒绝采样」的优势在于单次flip操作中只会调用一次随机方法。同时因为矩阵中最多只有1000个位置被翻转从随机点向两侧的扫描距离被已翻转位置数所限制复杂度具有保证。Java 参考实现来自原题解class Solution { int m, n; SetInteger set new HashSet(); Random random new Random(300); public Solution(int _m, int _n) { m _m; n _n; } public int[] flip() { int a random.nextInt(m * n), b a; while (a 0 set.contains(a)) a--; while (b m * n set.contains(b)) b; int c a 0 !set.contains(a) ? a : b; set.add(c); return new int[]{c / n, c % n}; } public void reset() { set.clear(); } }代码要点解析SetInteger set记录所有已被翻转的编号即值为1的格子不需要真实构建m * n的矩阵random.nextInt(m * n)在[0, m * n)内均匀随机一个编号a指针b从同一位置出发左侧指针a向左递减、右侧指针b向右递增跳过所有已在set中的编号最终优先取左侧找到的可用位置a否则取右侧的ba 0 !set.contains(a)的判断确保了选中的编号确实未被使用返回时将编号还原为坐标{c / n, c % n}reset只需清空set即可将所有格子重置为0。时间复杂度与空间复杂度令最大调用次数C 1000矩阵中最多有C个位置被翻转flip操作最坏复杂度为O(C)向两侧扫描经过所有已翻转位置reset复杂度为O(C)空间复杂度为O(C)用于存储set。解法二哈希表 swap随机区间始终连续解法一虽然在数据范围内可行但每次flip可能扫描多个已翻转位置最坏退化为O(C)。原始文档给出的更优做法是「哈希表 swap」核心目标是即使部分位置被翻转随机区间仍然保持连续每次仍能在[0, cnt)连续段内随机且单次flip严格O(1)。映射规则的设计起始时所有位置均未被翻转。规定未被翻转的位置其映射值为编号本身idx row * n col。由于未被翻转部分具有等值映射关系无需在哈希表中真实存储只记录被打破等值关系的映射。当随机到某个位置idx时分两种情况讨论原始文档的完整逻辑该位置未被哈希表真实记录未被翻转说明idx可被直接使用将idx作为本次随机点返回。同时把当前右端点尚未被使用位置的编号的映射值放到idx位置并将右端点左移一位。这样下次再随机到idx仍能直接取到idx的映射值随机区间的连续性得以维护该位置已被哈希表真实记录已被翻转此时idx里存的是上一次交换时的右端点映射值直接使用它即可然后用新的右端点映射值将其覆盖并更新右端点。同样保证了下次随机到idx时仍能直接取到有效映射。为什么这样能保证等概率整个算法的精髓在于[0, cnt)区间内每个位置始终对应一个尚未被使用的真实编号且这种对应是双射。每次flip相当于在[0, cnt)内均匀随机一个下标x取出x映射到的真实编号idx未被翻转过的位置映射值即自身将idx标记为已使用——具体做法是把区间最右端位置cnt - 1的映射值搬移到x上然后区间右端点左移cnt--。这正是经典数组尾部元素交换删除的哈希表版本因为每次都从尾部取一个未使用的编号来填补被随机走的位置所以区间[0, cnt)中的每个位置始终对应一个真实可用的格子随机范围随cnt同步收缩每个剩余格子被选中的概率自然均等。完整代码class Solution { int m, n, cnt; // cnt 为剩余数个数同时 cnt - 1 为区间右端点位置 MapInteger, Integer map new HashMap(); Random random new Random(300); public Solution(int _m, int _n) { m _m; n _n; cnt m * n; } public int[] flip() { int x random.nextInt(cnt--); int idx map.getOrDefault(x, x); map.put(x, map.getOrDefault(cnt, cnt)); return new int[]{idx / n, idx % n}; } public void reset() { cnt m * n; map.clear(); } }逐行解读这段非常精简的代码cnt m * n记录剩余可用格子数同时cnt - 1就是当前随机区间的右端点random.nextInt(cnt--)先在[0, cnt)内随机一个下标x随即cnt减一等价于先把右端点位置cnt - 1纳入可交换池再收缩区间map.getOrDefault(x, x)取出x的真实映射若x从未被记录未被翻转映射值即自身xmap.put(x, map.getOrDefault(cnt, cnt))将右端点位置cnt收缩后的新右端点的映射值写到x上——若cnt未被记录其映射值即cnt自身。这一步完成了用尾部可用编号填补被随机走的位置的交换返回{idx / n, idx % n}将真实编号还原为二维坐标reset恢复cnt并清空map。复杂度分析flip操作中只有一次nextInt和常数次哈希表读写时间复杂度为O(1)reset需要清空哈希表复杂度为O(C)空间复杂度为O(C)C 1000为最大翻转次数哈希表最多记录C个映射。一个直观的模拟示例以原题示例m 3, n 1共3个格子编号0, 1, 2为例首次flipcnt 3随机x假设x 1idx 1将cnt收缩为2并把编号2的映射写入位置1。返回[1, 0]第二次flipcnt 2在0, 2)内随机。若又随机到x 1此时map.getOrDefault(1, 1)取出的是上次写入的映射值2即返回尚未使用的格子2同时用当前右端点cnt 1覆盖位置1的映射第三次flipcnt 1只能随机到x 0对应编号0。可见无论随机序列如何返回的编号始终是尚未翻转过的格子且每个剩余格子被选中的概率始终均等。两种解法的对比与选型建议维度双指针扫描哈希表 swap单次随机调用次数1 次1 次flip时间复杂度最坏O(C)向两侧扫描严格O(1)reset时间复杂度O(C)O(C)空间复杂度O(C)SetO(C)Map核心思想就近填补尾部交换填补维护区间连续适用场景翻转次数少的题设C 1000翻转次数大、追求单次严格O(1)两者都保证了单次flip只调用一次随机函数都优于朴素拒绝采样。区别在于双指针解法借助总翻转次数少的题设用扫描换实现简单哈希表 swap 解法通过映射维护随机区间的连续性把flip降到严格O(1)在翻转次数接近矩阵大小时依然不会出现性能退化。实际面试与工程场景中哈希表 swap 是更通用的答案。同源题扩展从 380 到 710 的「映射 交换」套路「哈希表 swap 维持连续随机区间」并非 519 题独有在仓库的刷穿系列中是一个可复用的通用范式[380. O(1) 时间插入、删除和获取随机元素%20时间插入、删除和获取随机元素中等.md)用哈希表记录值 - 数组下标删除时将末尾元素搬到被删位置确保[0, idx]区间内都是存活值getRandom直接在连续区间内随机。这与 519 题解法二的尾部交换思想完全同源黑名单中的随机数从[0, n)中排除黑名单后随机。解法二将[0, n - m)内被禁用的数映射到[n - m, n)内可选的数上用两个Set区分范围、用Map记录映射把带黑名单的随机转化为连续区间内的随机同样体现了区间压缩 哈希映射的套路。三者放在一起可以看到一条清晰的进阶路径先用双指针/拒绝采样保证正确性再用哈希表 交换把随机区间压缩为连续段实现严格的O(1)随机。此外本仓库的 Index/哈希表.md 与 Index/双指针.md 将 519 题分别收录进「哈希表」和「双指针」两个 Tag 索引中读者可按标签体系系统检索同类题目。小结LeetCode 519「随机翻转矩阵」考察的是无放回等概率抽样在受限空间下的实现。本仓库题解给出的两条主线值得牢记二维转一维idx row * n col的编号映射把矩阵问题规约为一维区间问题连续区间维护用「双指针就近填补」或「哈希表 尾部交换」两种手段在部分元素被移除后依然保证随机区间的连续性从而做到单次随机调用与均等概率。其中解法二「哈希表 swap」在时间和空间上均达到最优且与 380、710 等题目共享同一套思维模型是随机化 哈希表类问题中值得反复练习的模板级解法。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐LogicStack-LeetCode 刷穿 LeetCode 第 13 题罗马数字转整数模拟与哈希表双解法详解LogicStack LeetCode 刷穿 LeetCode 第 13 题罗马数字转整数模拟与哈希表双解法详解 本篇技术指南基于仓库 LogicStac教程文档LogicStack-LeetCode 题解精读LeetCode 138「复制带随机指针的链表」——哈希表映射与原地 O(1) 空间两种深拷贝方案LogicStack LeetCode 题解精读LeetCode 138「复制带随机指针的链表」——哈希表映射与原地 O 1 空间两种深拷贝方案 本篇文章基于教程文档AlgoNote 题解LeetCode 0519 随机翻转矩阵哈希表 映射交换实现等概率不重复随机AlgoNote 题解LeetCode 0519 随机翻转矩阵哈希表 映射交换实现等概率不重复随机 导读 本篇基于《算法通关手册》AlgoNote教程文档知识库上一篇EmbedAI安全特性深度剖析为什么你的数据永远不会离开本地环境下一篇simplewall静默安装方法企业部署实用指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考