约瑟夫环

约瑟夫环问题是什么？

• 场景: $n$ 个人围成一圈, 从起点开始每数到第 $m$ 个人就淘汰, 求最后留下的人;
• 直接模拟: 用循环队列或链表逐个淘汰, 时间 $O(nm)$;
• 递推解法: 用公式把 $n$ 人问题的答案由 $n-1$ 人问题推出, 时间 $O(n)$;

约瑟夫环的递推公式如何推导？

• 设 $f(i)$ 为 $i$ 个人时的幸存者下标 (0 基);
• 淘汰第一个人后, 剩余 $i-1$ 人形成新的环, 原问题与新问题相差 $m$ 个位置;
• 关系: $f(i) = (f(i-1) + m) \bmod i$;
• 边界: $f(1) = 0$;

如何用一行循环求解约瑟夫环？

const iceBreakingGame = (num, target) => {
  let res = 0; // f(1) = 0
  for (let i = 2; i <= num; i++) {
    res = (res + target) % i; // f(i) = (f(i-1) + m) % i
  }
  return res;
};

• 复杂度: 时间 $O(n)$, 空间 $O(1)$;
• 口径: 返回值为 0 基下标, 若题目要求 1 基需再加 1;