1. 题目

0,1,…,n-1 这 n 个数字排成一个圆圈，从数字 0 开始每次从这个圆圈里删除第 m 个数字。求出这个圆圈里剩下的最后一个数字。

2. 思路分析

这个其实是经典的“约瑟夫环”问题。常用解法就是“循环取余”。每次都把下标移动 m 个位置，然后移除当前元素。直到只剩最后一个元素。

3. 代码实现

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
/**
 * @param {Number} n 0, 1, 2, ..., n-1 一共n个数字
 * @param {Number} m 被删除的第m个数字(从0计算)
 */
function lastRemain(n, m) {
    // 生成 [0, 1, ... , n-1] 的列表
    const nums = new Array(n)
    for (let i = 0; i < n; ++i) {
        nums[i] = i
    }

    // 逐步移除第m个数字
    let start = 0
    while (nums.length > 1) {
        start = (start + m) % nums.length
        nums.splice(start, 1)
    }

    return nums.shift()
}

/**
 * 测试函数
 */
console.log(lastRemain(5, 2))