自律小屋 | 自律小屋

解题思路：

模拟整个删除过程最直观，即构建一个长度为 $n$ 的链表，各节点值为对应的顺序索引；每轮删除第 $k$ 个节点，直至链表长度为 1 时结束，返回最后剩余节点的值即可。

模拟法需要循环删除 $n - 1$ 轮，每轮在链表中寻找删除节点需要 $k$ 次访问操作（链表线性遍历），因此总体时间复杂度为 $O(nm)$ 。题目给定的 $k, n$ 取值范围如下所示，观察可知此时间复杂度是不可接受的。

$$ 1 \leq n \leq 10^5 \ 1 \leq k \leq 10^6 $$

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

输入 $n, k$ ，记此约瑟夫环问题为「$n, k$ 问题」，设解（即最后留下的数字）为 $f(n)$ ，则有：

「$n, k$ 问题」：数字环为 $0, 1, 2, ..., n - 1$ ，解为 $f(n)$ 。
「$n-1, k$ 问题」：数字环为 $0, 1, 2, ..., n - 2$ ，解为 $f(n-1)$ 。
以此类推……

请注意，数字环是 首尾相接 的，为方便行文，本文使用列表形式表示。

对于「$n, k$ 问题」，首轮删除环中第 $k$ 个数字后，得到一个长度为 $n - 1$ 的数字环。由于有可能 $k > n$ ，因此删除的数字为 $(k - 1) % n$ ，删除后的数字环从下个数字（即 $k % n$ ）开始，设 $t = k % n$ ，可得数字环：

$$ t, t + 1, t + 2, ..., 0, 1, ..., t - 3, t - 2 $$

删除一轮后的数字环也变为一个「$n-1, k$ 问题」，观察以下数字编号对应关系：

$$ \begin{aligned} 「n-1, k 问题」 && \rightarrow && 「n, k 问题」删除后 \ 0 && \rightarrow && t + 0 \ 1 && \rightarrow && t + 1 \ ... && \rightarrow && ... \ n - 2 && \rightarrow && t - 2 \ \end{aligned} $$

设「$n-1, k$ 问题」某数字为 $x$ ，则可得递推关系：

$$ x \rightarrow (x + t) % n \ $$

换而言之，若已知「$n-1, k$ 问题」的解 $f(n - 1)$ ，则可通过以上公式计算得到「$n, k$ 问题」的解 $f(n)$ ，即：

$$ \begin{aligned} f(n) & = (f(n - 1) + t) % n \ & = (f(n - 1) + k % n) % n \ & = (f(n - 1) + k) % n \end{aligned} $$

以 $n = 5$ , $k = 3$ 的示例如下图所示。

$f(n)$ 可由 $f(n - 1)$ 得到，$f(n - 1)$ 可由 $f(n - 2)$ 得到，……，$f(2)$ 可由 $f(1)$ 得到；因此，若给定 $f(1)$ 的值，就可以递推至任意 $f(n)$ 。而「$1, k$ 问题」的解 $f(1) = 0$ 恒成立，即无论 $k$ 为何值，长度为 1 的数字环留下的是一定是数字 $0$ 。

以上数学推导本质是得出动态规划的转移方程和初始状态。

算法流程：

状态定义： 设「$i, k$ 问题」的解为 $dp[i]$ 。
转移方程： 通过以下公式可从 $dp[i - 1]$ 递推得到 $dp[i]$ 。

$$ dp[i] = (dp[i - 1] + k) % i $$

初始状态：「$1, k$ 问题」的解恒为 $0$ ，即 $dp[1] = 0$ 。
返回值： 返回「$n, k$ 问题」的解 $dp[n]$ 。

如下图所示，为 $n = 5$ , $k = 3$ 时的状态转移和对应的模拟删除过程。

代码：

根据状态转移方程的递推特性，无需建立状态列表 $dp$ ，而使用一个变量 $x$ 执行状态转移即可。

Python

class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        x = 0
        for i in range(2, n + 1):
            x = (x + k) % i
        return x + 1

Java

class Solution {
    public int findTheWinner(int n, int k) {
        int x = 0;
        for (int i = 2; i <= n; i++) {
            x = (x + k) % i;
        }
        return x + 1;
    }
}

C++

class Solution {
public:
    int findTheWinner(int n, int k) {
        int x = 0;
        for (int i = 2; i <= n; i++) {
            x = (x + k) % i;
        }
        return x + 1;
    }
};

复杂度分析：

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

解题思路： ​

算法流程： ​

代码： ​

复杂度分析： ​

解题思路：

算法流程：

代码：

复杂度分析：