0384. Shuffle an Array ====================== 题目信息 -------- :题号: 0384 :难度: Medium :主题: 设计、数组排列、均匀随机、重置状态 :原题: `LeetCode 0384 `_ :重点: ``reset`` 恢复构造时顺序、``shuffle`` 返回随机排列、所有排列概率相同、对象跨调用保留初始数组 题目重述 -------- 使用整数数组 ``nums`` 构造对象,并实现两个操作。``reset()`` 返回数组构造时的原始顺序;``shuffle()`` 返回由相同元素组成的一个随机排列,并要求所有可能排列出现的概率相同。 数组长度位于 ``[1, 50]``,元素位于 ``[-10^6, 10^6]``,且所有元素互不相同;对 ``reset`` 和 ``shuffle`` 的调用总数不超过 ``10^4``。无论此前进行了多少次洗牌,``reset`` 都必须依据构造时的初始顺序,而不是最近一次随机结果。 自建示例 -------- 洗牌后恢复原始顺序: .. code-block:: text 初始数组:nums = [2,5,9] 调用:shuffle(), reset() 输出:shuffle 可以返回 [9,2,5] 等任意排列;reset 返回 [2,5,9] 解释:三个元素的六种排列应等概率出现,重置结果始终是构造时顺序。 单元素数组: .. code-block:: text 初始数组:nums = [-4] 调用:shuffle(), reset() 输出:[-4],[-4] 解释:只有一种排列,两种操作都返回相同内容。 Fisher–Yates 逐步确定随机位置 ------------------------------ 从数组末尾向前处理位置 ``i``,在尚未确定的 ``[0, i]`` 中等概率选择一个位置并交换。第 ``i`` 位的每个元素都有 ``1/(i+1)`` 的机会被选中,递推得到所有完整排列等概率。每次洗牌都从原始数组复制一份,避免上一次随机结果影响下一次。 C++ 实现 -------- .. code-block:: cpp class Solution { std::vector original; std::mt19937 generator{std::random_device{}()}; public: Solution(std::vector& nums) : original(nums) {} std::vector reset() { return original; } std::vector shuffle() { std::vector result = original; for (int i = static_cast(result.size()) - 1; i > 0; --i) { std::uniform_int_distribution distribution(0, i); int chosen = distribution(generator); std::swap(result[i], result[chosen]); } return result; } }; 代码分析 -------- ``reset`` 返回从未修改的 ``original`` 副本;Fisher–Yates 每一步只在尚未固定的前缀中抽样,不会产生排列偏斜。洗牌时间为 ``O(n)``,复制结果的额外空间为 ``O(n)``,重置也需要复制返回值。