🔖 quiz经典问题约瑟夫环

经典约瑟夫环问题

有 N 个人围坐成一圈，任选某个人将其编号为 0，其右手边的人编号为 1，以此类推，将全部 N 个人进行唯一编号。由编号为 0 的人从 1 开始报数，其右手边的人报下一个数，以此类推。报到 M 的人起身离开，TA 右手边的人又从 1 开始报数，直到所有人起身离开，求最后一个起身离开的人的编号。

暴力法

使用链表进行模拟，起身离开的复杂度为 O(1)，报数的复杂度为 O(M)，故总复杂度为：

  • 时间复杂度： O(M⋅N)
  • 额外空间复杂度： O(N)

树状数组

用一个数组 A 表示这 N 个人当前的游戏状态：

  • A[i]=1: 编号为 i 的人还坐在那里
  • A[i]=0: 编号为 0 的人已经起身离开

则可以使用树状数组维护前缀和[1]，报数相当于快速找到某个指定位置开始的区间 [l,r]，使得 ∑i=lrA[i]=M.

在前期 A 数组中 1 的密度浓的时候，单次报数的复杂度接近于 O(log⁡N) （即少数几次树状数组的查询）；但在游戏后期，A 数组中密度低的时候，单次报数的复杂度可能退化为 O(Mlog⁡N) ，故总复杂度为：

  • 时间复杂度（宽松上界）： O(M⋅min{N,M}⋅log⁡N)
  • 额外空间复杂度： O(N)
01.ts  | 21 lines.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import { type BinarySearchTree, createBinarySearchTree } from './bit'


export function lastRemaining(N: number, M: number): number {
  if (N <= 0) return -1
  if (N === 1) return 1


  const bit: BinarySearchTree = createBinarySearchTree(N)
  for (let i = 1; i <= N; ++i) bit.add(i, 1)


  let p = 0
  for (let n = N; n > 0; --n) {
    let total = M % n
    for (total = total === 0 ? M : total; total > 0; ) {
      const _end = Math.min(N, p + total)
      total -= bit.sum(_end) - bit.sum(p)
      p = _end === N ? 0 : _end
    }
    bit.add(p === 0 ? N : p, -1)
  }
  return (p + N - 1) % N
}

树状数组 + 二分

为了快速跳过中间的 0，我们可以通过二分的方式快速确定下一次树状数组需要查询的位置，则单次报数的复杂度为 O(log2⁡N)，总复杂度为：

  • 时间复杂度： O(N⋅log2⁡N)
  • 额外空间复杂度： O(N)

下面的代码中假定当三分之一的人起身离开后，A 数组中 1 密度足够多，即阈值为 2N3，（可以自己调试阈值）。当人数少于阈值后，开始使用二分确定下一步查询的位置。实践证明优化后的代码比优化前快了一倍多。

02.ts  | 37 lines.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import { type BinarySearchTree, createBinarySearchTree } from './bit'


export function lastRemaining(N: number, M: number): number {
  if (N <= 0) return -1
  if (N === 1) return 1


  const bit: BinarySearchTree = createBinarySearchTree(N)
  for (let i = 1; i <= N; ++i) bit.add(i, 1)


  let p = 0
  for (let n = N, threshold = Math.round((N * 2) / 3); n > 0; --n) {
    let total = M % n
    for (total = total === 0 ? M : total; total > 0; ) {
      let _end = p + total
      const target = total + bit.sum(p)


      if (n < threshold) {
        if (_end < N) {
          let lft = _end
          let rht = N + 1
          while (lft < rht) {
            const mid = (lft + rht) >> 1
            if (bit.sum(mid) < target) lft = mid + 1
            rht = mid
          }
          _end = lft < N ? lft : N
        }
      }


      if (_end > N) _end = N
      total = target - bit.sum(_end)
      p = _end === N ? 0 : _end
    }
    bit.add(p === 0 ? N : p, -1)
  }
  return (p + N - 1) % N
}

递推

考虑这样一种操作：每次有人起身离开时，将TA右手边的人重新编号为 0，右手边的右手边的人重新编号为 1，……，以此类推。

为方便表述，不妨记圈中剩余 n 个人时，即将起身离开的人在此轮中的编号为 h(n)，在上一轮的编号为 h′(n)。根据游戏规则，不难有：当某轮游戏中只剩下 n 个人时，即将起身离开的人在这一轮中的编号为 h(n)=M−1modn；下一轮进行重新编号时，将此时编号为 h(n)+kmodn （其中 1⩽k<n）的人重新编号为 k−1。特别地，当 k=M 时，根据映射关系有：

h(n)+Mmodn≡(M−1)mod(n−1)→h(n−1)

即 h′(n−1)≡h(n)+Mmodn，也就是：游戏进行到剩余 n−1 个人时，即将离开的人其在上一轮的编号为当前编号 +M 再对 n 取模。而当游戏仅剩下一个人时，此时离开的人即为原问题中最后一个离开的人，也就是我们只要求出 h(1) 在游戏初始时的编号就可以了。

不妨设 f(n) 表示原问题中最后一个起身离开的人在剩下 n 个人时那一轮游戏中的编号，则所求答案为 f(N)。根据上述分析不难得到递推方程：

f(n)={0,n=1f(n−1)+Mmodn,n>1

由 f 的定义可以看出来，递推法求解约瑟夫环问题可以在 O(N) 的复杂度下求出最后一个离开的人的编号，但不能求出整个游戏中的离场顺序。若要求出倒数第二个人离场的人的编号，只要改一下递推方程的初始条件就好了：

f(n)={M+1modn,n=2f(n−1)+Mmodn,n>1

  • 递推写法

    • 时间复杂度： O(N)
    • 额外空间复杂度： O(1)
    03.ts  | 6 lines.
    1
    2
    3
    4
    5
    6
    export function lastRemaining(N: number, M: number): number {
      if (N <= 0) return -1
      let ans = 0
      for (let n = 2; n <= N; ++n) ans = (ans + M) % n
      return ans
    }

  • 递归写法

    • 时间复杂度： O(N)
    • 额外空间复杂度： O(N)
    04.ts  | 10 lines.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    export function lastRemaining(N: number, M: number): number {
      if (N <= 0) return -1
      return round(N)
    

      function round(n: number): number {
        if (n === 1) return 0
        const y = round(n - 1)
        return (y + M) % n
      }
    }

不定步长的约瑟夫问题

在经典约瑟夫问题的基础上，每次起身离开的人报的的数不同。其中第 i 个起身的人需要报到的数为 Mi。

不难发现，前面提到的 暴力法、前缀和-树状数组 算法仍然适用。这里仅就 递推法 进行讨论。

递推

对比游戏规则，不难想到上文中提到的映射关系

h(n)+Mmodn≡(M−1)mod(n−1)→h(n−1)

需要更新为

h(n)+MN−nmodn≡(MN−n−1)mod(n−1)→h(n−1)

则不难得到新的递推方程：

f(n)={0,n=1f(n−1)+MN−nmodn,n>1

  • 递推写法

    • 时间复杂度： O(N)
    • 额外空间复杂度： O(1)
    05.ts  | 6 lines.
    1
    2
    3
    4
    5
    6
    export function lastRemaining(N: number, M: number[]): number {
      if (N <= 0) return -1
      let ans = 0
      for (let n = 2; n <= N; ++n) ans = (ans + M[N - n]) % n
      return ans
    }

  • 递归写法

    • 时间复杂度： O(N)
    • 额外空间复杂度： O(N)
    06.ts  | 10 lines.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    export function lastRemaining(N: number, M: number[]): number {
      if (N <= 0) return -1
      return round(N)
    

      function round(n: number): number {
        if (n === 1) return 0
        const y = round(n - 1)
        return (y + M[N - n]) % n
      }
    }
footnote-definitions

  • ↑ [1]: 

    为了方便树状数组操作，处理时将所有人的编号 +1，在计算答案时再 −1

© 2017-2026 光和尘有花满渚、有酒盈瓯

Comments