洗牌算法

如何等概率地打乱数组？

• 目标: n 个位置中, 每个元素落到任意位置的概率相同;
• 从最后一个位置开始倒序遍历, 把位置 i 与 [0, i] 中的随机下标交换;
• 交换后位置 i 的元素不再参与后续抽取;

function shuffle(nums: number[]): number[] {
  for (let i = nums.length - 1; i >= 0; i--) {
    const index = Math.floor(Math.random() * (i + 1));
    [nums[i], nums[index]] = [nums[index], nums[i]];
  }
  return nums;
}

为什么每轮的随机范围必须缩小？

• 第 i 轮在 [0, i] 中随机, 保证位置 i 取到剩余任一元素的概率都是 1/(i+1);
• 若每轮都在 [0, n-1] 中随机, 分布会不均匀;
• 也可正序遍历, 让位置 i 与 [i, n-1] 中的随机下标交换, 效果相同;

如何在打乱的同时支持重置？

• 用两个数组: origin 保存初始状态, state 保存当前状态;
• reset: 由 origin 复制回 state;
• shuffle: 只修改 state;

class Solution {
  private origin: number[];
  private state: number[];

  constructor(nums: number[]) {
    this.origin = [...nums];
    this.state = [...nums];
  }

  reset(): number[] {
    this.state = [...this.origin];
    return this.state;
  }

  shuffle(): number[] {
    for (let i = this.state.length - 1; i >= 0; i--) {
      const index = Math.floor(Math.random() * (i + 1));
      [this.state[i], this.state[index]] = [this.state[index], this.state[i]];
    }
    return this.state;
  }
}

洗牌算法的复杂度是多少？

• 时间复杂度: O(n), 每轮一次交换;
• 空间复杂度: O(n), origin 与 state 各一份;