【Leetcode】1823. Find the Winner of the Circular Game（配数学证明）

题目地址：

https://leetcode.com/problems/find-the-winner-of-the-circular-game/description/

给定$n$个人编号$1\sim n$，再给定一个正整数$k<n$，从$1$开始报数，报到$k$的人出列，再继续从$1$报数，每次报到$k$的人出列。问最后剩下的人编号是多少。

设$f(n)$是$n$个人的情况下剩下的人的编号，第一轮之后剩下的人为$k+1,k+2,...,n-1,n,...,k-1$，我们将这些数与$1,2,...,n-1$进行映射，即将$1\to k+1,2\to k+2,...,n-1\to k-1$，这种映射表达式为$g(a)=(a+k-1)\%n+1$，所以：$$f(n)=(f(n-1)+k-1)\%n+1$$初始条件$f(1)=1$。代码如下：

class Solution {
 public:
  int findTheWinner(int n, int k) {
    if (n == 1) return 1;
    return (findTheWinner(n - 1, k) + k - 1) % n + 1;
  }
};
1
2
3
4
5
6
7

时空复杂度$O(n)$。