---

comments: true
difficulty: 简单
edit_url: https://github.com/doocs/leetcode/edit/main/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9862.%20%E5%9C%86%E5%9C%88%E4%B8%AD%E6%9C%80%E5%90%8E%E5%89%A9%E4%B8%8B%E7%9A%84%E6%95%B0%E5%AD%97/README.md

面试题 62. 圆圈中最后剩下的数字

题目描述

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)$ 表示从 $n$ 个数中每次删除第 $m$ 个，最后剩下的是第几个数字。

我们第一次删除了第 $m$ 个数字，剩下 $n-1$ 个数，那么 $x=f(n-1,m)$ 就表示从剩下的 $n-1$ 个数中，每次删除第 $m$ 个，最后剩下的是第几个数字。

我们求得 $x$ 之后，便可以知道 $f(n,m)$ 应该是从 $m\%n$ 开始数的第 $x$ 个元素，即 $f(n,m)=(m\%n+x)\%n$。

当 $n$ 为 $1$ 时，最后留下的数字序号一定为 $0$。

递归求解即可，也可以改成迭代。

时间复杂度 $O(n)$，递归的空间复杂度 $O(n)$，迭代的空间复杂度 $O(1)$。

题解：https://www.acwing.com/video/205/

Python3

class Solution:def lastRemaining(self, n: int, m: int) -> int:def f(n, m):if n == 1:return 0return (f(n - 1, m) + m) % nreturn f(n, m)

Java

class Solution {public int lastRemaining(int n, int m) {return f(n, m);}private int f(int n, int m) {if (n == 1) {return 0;}int x = f(n - 1, m);return (m + x) % n;}
}

C++

class Solution {
public:int lastRemaining(int n, int m) {return f(n, m);}int f(int n, int m) {if (n == 1) {return 0;}int x = f(n - 1, m);return (m + x) % n;}
};

Go

func lastRemaining(n int, m int) int {var f func(n, m int) intf = func(n, m int) int {if n == 1 {return 0}x := f(n-1, m)return (m + x) % n}return f(n, m)
}

JavaScript

/*** @param {number} n* @param {number} m* @return {number}*/
var lastRemaining = function (n, m) {let f = 0;for (let i = 2; i <= n; ++i) {f = (f + m) % i;}return f;
};

C#

public class Solution {public int LastRemaining(int n, int m) {int f = 0;for (int i = 2; i < n + 1; i++) {f = (f + m) % i;}return f;}
}

Swift

class Solution {func lastRemaining(_ n: Int, _ m: Int) -> Int {return f(n, m)}private func f(_ n: Int, _ m: Int) -> Int {if n == 1 {return 0}let x = f(n - 1, m)return (m + x) % n}
}

方法二

Python3

class Solution:def lastRemaining(self, n: int, m: int) -> int:f = 0for i in range(2, n + 1):f = (f + m) % ireturn f

Java

class Solution {public int lastRemaining(int n, int m) {int f = 0;for (int i = 2; i <= n; ++i) {f = (f + m) % i;}return f;}
}

C++

class Solution {
public:int lastRemaining(int n, int m) {int f = 0;for (int i = 2; i <= n; ++i) {f = (f + m) % i;}return f;}
};

Go

func lastRemaining(n int, m int) int {f := 0for i := 2; i <= n; i++ {f = (f + m) % i}return f
}