leetcode-1823. 找出游戏的获胜者

首先我们定义 \(f(n,m)\) 表示 \(n\) 个人中，每数到 \(m\) 就淘汰一个人，最后剩下的那个人的编号。

当只有一个人的时候，那么他一定是最后留下的，即 \(f(1,m)=0\)。

当有两个人的时候，那么第一个人被淘汰之后，剩下的那个人就是最后留下的，即 \(f(2,m)=(f(1,m)+m)\bmod 2\)。

当有 \(n\) 个人的时候，我们假设最后留下的那个人的初始编号为 \(k\)，那么第一轮淘汰之后，第 \(m\) 个人就会被淘汰，剩下的 \(n-1\) 个人构成了一个新的数列，而且初始编号从 \(k+1\) 开始，即成为了一个以 \(k+1\) 为起点的编号从 \(0\) 开始的数列。根据归纳假设，这个数列中最后剩下的那个人的编号是 \(f(n-1,m)\)。由于第一个淘汰的人的编号是 \((k+m-1)\bmod n\)，所以相对于初始编号 \(k+1\)，他的编号是 \(((k+m-1)\bmod n)-1\)。而因为他被淘汰了，所以剩下的编号从 \((k+m)\bmod n\) 开始。于是我们可以得到下面的递推式：

\[ f(n,m)=(f(n−1,m)+m)modn \]

最终的答案即为 \(f(n,m)\)。

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