lastRemaining.md

圆圈中最后剩下的数字

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

例如，0、1、2、3、4 这 5 个数字组成一个圆圈，从数字 0 开始每次删除第 3 个数字，则删除的前 4 个数字依次是 2、0、4、1，因此最后剩下的数字是 3。

示例 1：

// 输入: n = 5, m = 3
// 输出: 3

示例 2：

// 输入: n = 10, m = 17
// 输出: 2

限制:

• 1 <= n <= 10 ^ 5
• 1 <= m <= 10 ^ 6

思路分析

本题是著名的约瑟夫环问题。而这个问题有一个公式，即:

f(n,m) = (f(n - 1) + m) % n

只要知道了这个公式，就非常简单了，接下来，我们来看是如何推导出这个公式的。

首先我们应该知道，本题 n 一定是大于 1 的，因为 n = 1 时，就是最后剩下的数字，无论 m 是什么值，此时编号就为 0，记为 f(1) = 0。因此，n 个数字中删除第 m 个数字的值一定是(m - 1) % n。其中 m - 1 表示下标，比如 0,1,2,3,4 删除第 3 个数字就是(3 - 1) % 5 = 2。删除了这个数字后，接下来就构成了一个 n - 1 长度的环。可以记为:0,1,3,4 接下来我们从删除后的下一个数字开始计数，也就是说从下一个数字 m % n 开始，我们记为 t。因此这个 n - 1 的环，我们就可以表示成 t,t + 1,t + 2,... t - 3,t - 2。例如 0,1,2,3,4 删除 2 之后，从下一个数字 3 开始，就变成了 3,3 + 1,3 - 3,3 - 2（3,4,0,1）。对应映射关系如下所示:

[n - 1,m]问题		[n,m]问题
0	-->	t + 0
1	-->	t + 1
2	-->	t + 2
...	-->	...
n - 2	-->	t - 2

根据如上映射关系，设[n - 1,m]问题某个数字为 x，则可以得到递推公式为 x -> (x + t) % n。我们假设 f(n - 1)为[n - 1,m]问题的解，则可以推导出 f(n) = (x + t) % n = (f(n - 1) + t) % n = (f(n - 1) + m % n ) % n = (f(n - 1) + m) % n。

根据以上公式，我们就可以写出如下代码来解决这道题。

/**
 * @param {number} n
 * @param {number} m
 * @return {number}
 */
var lastRemaining = function (n, m) {
  let res = 0,
    i = 1; //初始值为0
  while (++i < n + 1) {
    // 根据公式f(n,m) = (f(n - 1) + m) % n;,这里的n就是指编号，即下标
    res = (res + m) % i;
  }
  return res;
};

时间复杂度 O(n)： 状态转移循环 n - 1 次使用 O(n) 时间，状态转移方程计算使用 O(1) 时间； 空间复杂度 O(1)： 使用常数大小的额外空间；

更多详细解题思路参考题解。