1. 题目

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

2. 思路分析

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

3. 代码实现

/**
 * @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));
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