Medium

题目描述

有 n 个朋友在玩游戏。朋友们围成一圆圈，按顺时针方向从 1 到 n 编号。更正式地说，从第 i 个朋友顺时针移动会到达第 (i+1) 个朋友（当 1 <= i < n 时），而从第 n 个朋友顺时针移动会到达第 1 个朋友。

游戏规则如下：

  1. 从第 1 个朋友开始。
  2. 沿顺时针方向数 k 个朋友，包括起始的朋友。计数会绕圆圈进行，可能会重复计数某些朋友。
  3. 你数到的最后一个朋友离开圆圈，游戏失败。
  4. 如果圆圈中仍有超过一个朋友，则回到步骤 2，从刚刚离开的朋友顺时针方向的下一个朋友开始，重复此过程。
  5. 否则，圆圈中的最后一个朋友获胜。

给定朋友数量 n 和整数 k，返回游戏的获胜者。

示例 1：

输入：n = 5, k = 2
输出：3
解释：游戏运行步骤如下：
1) 从朋友 1 开始。
2) 顺时针数 2 个朋友，也就是朋友 1 和 2 。
3) 朋友 2 离开圆圈。下一次从朋友 3 开始。
4) 顺时针数 2 个朋友，也就是朋友 3 和 4 。
5) 朋友 4 离开圆圈。下一次从朋友 5 开始。
6) 顺时针数 2 个朋友，也就是朋友 5 和 1 。
7) 朋友 1 离开圆圈。下一次从朋友 3 开始。
8) 顺时针数 2 个朋友，也就是朋友 3 和 5 。
9) 朋友 5 离开圆圈。只剩下朋友 3，所以朋友 3 是获胜者。

示例 2：

输入：n = 6, k = 5
输出：1
解释：朋友离开的顺序：5、4、6、2、3。获胜者是朋友 1。

提示：

  • 1 <= k <= n <= 500

解题思路

这是经典的约瑟夫环问题。我们可以用多种方法来解决：

方法一：模拟（推荐）

最直观的方法是直接模拟游戏过程。维护一个列表记录当前圆圈中的朋友，每轮游戏从当前位置开始数 k 个人，移除第 k 个人，然后继续下一轮。

使用列表模拟的优点是思路清晰，易于理解和实现。

方法二：约瑟夫环数学公式

约瑟夫环有一个经典的数学递推公式：J(n,k) = (J(n-1,k) + k) % n，其中 J(n,k) 表示 n 个人中第 k 个被淘汰时最后剩余的人的位置（从0开始编号）。

基本思路是：如果我们知道 n-1 个人时的答案，那么当有 n 个人时，由于多了一个人，所有位置都会向后偏移，我们可以通过数学关系推导出 n 个人的答案。

方法三：递归

基于数学公式，我们也可以用递归的方式来解决，递归的基础情况是只有1个人时，获胜者就是第0个位置的人。

考虑到题目要求和理解难度，这里推荐使用模拟方法，它最直观且性能足够好。

代码实现

class Solution {
public:
    int findTheWinner(int n, int k) {
        vector<int> friends;
        for (int i = 1; i <= n; i++) {
            friends.push_back(i);
        }
        
        int index = 0;
        while (friends.size() > 1) {
            index = (index + k - 1) % friends.size();
            friends.erase(friends.begin() + index);
        }
        
        return friends[0];
    }
};

class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        friends = list(range(1, n + 1))
        index = 0
        
        while len(friends) > 1:
            index = (index + k - 1) % len(friends)
            friends.pop(index)
        
        return friends[0]

public class Solution {
    public int FindTheWinner(int n, int k) {
        List<int> friends = new List<int>();
        for (int i = 1; i <= n; i++) {
            friends.Add(i);
        }
        
        int index = 0;
        while (friends.Count > 1) {
            index = (index + k - 1) % friends.Count;
            friends.RemoveAt(index);
        }
        
        return friends[0];
    }
}

var findTheWinner = function(n, k) {
    let friends = [];
    for (let i = 1; i <= n; i++) {
        friends.push(i);
    }
    
    let index = 0;
    while (friends.length > 1) {
        index = (index + k - 1) % friends.length;
        friends.splice(index, 1);
    }
    
    return friends[0];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型模拟方法约瑟夫环公式
时间复杂度O(n²)O(n)
空间复杂度O(n)O(1)

说明：

  • 模拟方法：每轮需要删除一个元素，删除操作需要O(n)时间，总共进行n-1轮，所以时间复杂度为O(n²)
  • 约瑟夫环公式：只需要一次循环计算递推关系，时间复杂度为O(n)，空间复杂度为O(1)