剑指Offer题解 - Day55

剑指 Offer 62. 圆圈中最后剩下的数字

力扣题目链接[1]

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

「限制：」

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

思路：

首先考虑使用暴力法进行题解。假定0~n-1的是循环链表，那么我们只需要每次移动指针m次，将当前节点删除，然后重复动作。最终当链表只剩下一个节点时，直接返回即可。

此做法需要的时间复杂度是O(mn) ，由题目限制可以看出，此时间复杂度是不可以接受的。而且本方法无法通过提交，会超时。因此不考虑此方法。

动态规划

本题是著名的 “约瑟夫环” 问题，可使用 「动态规划」 解决。

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

• 时间复杂度 O(n)。
• 空间复杂度 O(1)。

分析：

我们假设[n,m]圆圈的最终解为f(n)，那么[n-1, m]圆圈的解就是f(n - 1)。直到[1, m]圆圈的解为f(1)。

对于初始状态[n,m]，删掉第m个数字后，就得到一个n-1的圆圈。因为有可能m > n，因此删除掉的数字是(m - 1)%n。而下一轮的第一个数字就会从m%n开始。

此时，m%n 所代表的就是第一轮中的第一位数字0。可以看出，第一位数字的递推公式为x →(x + m %n)%n 。

最终，得出动态转移方程：

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

对于初始值[1, m]，也就是圆圈里只有1个数字，最终返回的就是0。所以f(1) = 0 。

总结

本题考查动态规划。约瑟夫环的问题是经典的数学问题，部分同学包括我在内，可能都不太记得该问题。而且动态方程也比较难归纳，难度系数中级。

复杂度方面，n-1 次循环需要时间为O(n) ，声明变量占用常数级别的空间。

参考资料

[1]

力扣题目链接: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/oxrkot/