原文链接: https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof

中文题目

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

通过代码

高赞题解

解题思路：

这个问题是以弗拉维奥·约瑟夫命名的，他是1世纪的一名犹太历史学家。他在自己的日记中写道，他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘，最终决定自杀，并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人，他们将向罗马军队投降，不再自杀。约瑟夫斯把他的存活归因于运气或天意，他不知道是哪一个。 —— 【约瑟夫问题】维基百科

🙋 宝宝们我来了。。我是 Sweetiee 的小号。。。

模拟链表，$O(n^2)$

如果单纯用链表模拟的话，时间复杂度是 $O(nm)$ 的，可以看下题目的数据范围，肯定是不能这么做的。关于运行时间的预估，经验是如果 $n<10^5$ ，那么 $O(n^2)$ 的解法耗时大概是几秒左右（当然时间复杂度会忽略常数，而且也有可能由于执行程序的机器性能的不同，$O(n^2)$ 的实际耗时也有可能一秒多，也有可能十几秒）。本题由于 $1 <= m <= 10^6$ ，所以 $O(nm)$ 肯定是超时的。

可以分析下纯暴力的做法，每次找到删除的那个数字，需要 $O(m)$ 的时间复杂度，然后删除了 $n-1$ 次。但实际上我们可以直接找到下一个要删除的位置的！

假设当前删除的位置是 $idx$，下一个删除的数字的位置是 $idx + m$ 。但是，由于把当前位置的数字删除了，后面的数字会前移一位，所以实际的下一个位置是 $idx + m - 1$。由于数到末尾会从头继续数，所以最后取模一下，就是 $(idx + m - 1) \pmod n$。

至于这种思路的代码实现，我尝试了下 LinkedList 会超时，我猜是因为 LinkedList 虽然删除指定节点的时间复杂度是 $O(1)$ 的，但是在 remove 时间复杂度仍然是 $O(n)$ 的，因为需要从头遍历到需要删除的位置。那 ArrayList 呢？索引到需要删除的位置，时间复杂度是 $O(1)$，删除元素时间复杂度是 $O(n)$（因为后续元素需要向前移位）， remove 整体时间复杂度是 $O(n)$ 的。看起来LinkedList 和 ArrayList 单次删除操作的时间复杂度是一样的 ？所累哇多卡纳！ArrayList 的 remove 操作在后续移位的时候，其实是内存连续空间的拷贝的！所以相比于LinkedList大量非连续性地址访问，ArrayList的性能是很 OK 的！

这是 ArrayList 的 remove 源码：

每次删除的时间复杂度是 $O(n)$，删除了 $n-1$ 次，所以整体时间复杂度是 $O(n^2)$。leetcode 上该方法勉强可以通过，大概是 1s 多一点。
所以基于 ArrayList 的模拟链表实现代码如下:

[]
class Solution {
    public int lastRemaining(int n, int m) {
        ArrayList<Integer> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        int idx = 0;
        while (n > 1) {
            idx = (idx + m - 1) % n;
            list.remove(idx);
            n--;
        }
        return list.get(0);
    }
}

---

数学解法，$O(n)$

这么著名的约瑟夫环问题，是有数学解法的！
因为数据是放在数组里，所以我在数组后面加上了数组的复制，以体现是环状的。我们先忽略图片里的箭头：
【第一轮后面的数字应该是[0, 1, 2 ,3 ,4]，手误打错了。。抱歉】

很明显我们每次删除的是第 $m$ 个数字，我都标红了。

第一轮是 [0, 1, 2, 3, 4] ，所以是 [0, 1, 2, 3, 4] 这个数组的多个复制。这一轮 2 删除了。

第二轮开始时，从 3 开始，所以是 [3, 4, 0, 1] 这个数组的多个复制。这一轮 0 删除了。

第三轮开始时，从 1 开始，所以是 [1, 3, 4] 这个数组的多个复制。这一轮 4 删除了。

第四轮开始时，还是从 1 开始，所以是 [1, 3] 这个数组的多个复制。这一轮 1 删除了。

最后剩下的数字是 3。

图中的绿色的线指的是新的一轮的开头是怎么指定的，每次都是固定地向前移位 $m$ 个位置。

然后我们从最后剩下的 3 倒着看，我们可以反向推出这个数字在之前每个轮次的位置。

最后剩下的 3 的下标是 0。

第四轮反推，补上 $m$ 个位置，然后模上当时的数组大小 $2$，位置是(0 + 3) % 2 = 1。

第三轮反推，补上 $m$ 个位置，然后模上当时的数组大小 $3$，位置是(1 + 3) % 3 = 1。

第二轮反推，补上 $m$ 个位置，然后模上当时的数组大小 $4$，位置是(1 + 3) % 4 = 0。

第一轮反推，补上 $m$ 个位置，然后模上当时的数组大小 $5$，位置是(0 + 3) % 5 = 3。

所以最终剩下的数字的下标就是3。因为数组是从0开始的，所以最终的答案就是3。

总结一下反推的过程，就是 (当前index + m) % 上一轮剩余数字的个数。

代码就很简单了。

[]
class Solution {
    public int lastRemaining(int n, int m) {
        int ans = 0;
        // 最后一轮剩下2个人，所以从2开始反推
        for (int i = 2; i <= n; i++) {
            ans = (ans + m) % i;
        }
        return ans;
    }
}

以上谢谢大家，求赞求赞求赞！

统计信息

通过次数	提交次数	AC比率
116500	177677	65.6%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言