avatar

光和尘

有花满渚、有酒盈瓯

目录检索关于我

🔖 quiz经典问题约瑟夫环

经典约瑟夫环问题

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

暴力法

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

  • 时间复杂度: O(M \cdot N)
  • 额外空间复杂度: O(N)

树状数组

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

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

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

在前期 A 数组中 1 的密度浓的时候,单次报数的复杂度接近于 O(\log N) (即少数几次树状数组的查询);但在游戏后期,A 数组中密度低的时候,单次报数的复杂度可能退化为 O(M \log N) ,故总复杂度为:

  • 时间复杂度(宽松上界): O(M \cdot \min\{N, M\} \cdot \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 { 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(\log^2 N),总复杂度为:

  • 时间复杂度: O(N \cdot \log^2 N)
  • 额外空间复杂度: O(N)

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

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 { 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 - 1 \mod n;下一轮进行重新编号时,将此时编号为 h(n) + k \mod n (其中 1 \leqslant k < n)的人重新编号为 k-1。特别地,当 k=M 时,根据映射关系有:

h(n) + M \mod n \equiv (M - 1) \mod (n - 1) \quad\rightarrow\quad h(n-1)

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

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

f(n) = \left\lbrace \begin{aligned} &0, &n = 1\\ &f(n - 1) + M \mod n, &n > 1\\ \end{aligned}\right.

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

f(n) = \left\lbrace \begin{aligned} &M + 1 \mod n, &n = 2\\ &f(n - 1) + M \mod n, &n > 1\\ \end{aligned}\right.
  • 递推写法

    • 时间复杂度: 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 个起身的人需要报到的数为 M_i

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

递推

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

h(n) + M \mod n \equiv (M - 1) \mod (n - 1) \quad\rightarrow\quad h(n-1)

需要更新为

h(n) + M_{N-n} \mod n \equiv (M_{N-n} - 1) \mod (n - 1) \quad\rightarrow\quad h(n-1)

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

f(n) = \left\lbrace \begin{aligned} &0, &n = 1\\ &f(n - 1) + M_{N-n} \mod n, &n > 1\\ \end{aligned}\right.
  • 递推写法

    • 时间复杂度: 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
    }
    }
© 2017-2022 光和尘有花满渚、有酒盈瓯

Comments