找出游戏的获胜者 图解题解
这道题到底在问什么
- 输入
- n=5, k=2
- 输出
- 3
- 输入
- n=6, k=5
- 输出
- 1
- 输入
- n=1, k=1
- 输出
- 1
先想最直接的笨办法
换个角度验证一下。这类围圈报数有条漂亮的递推:只有 1 个人时获胜者就是 1 号;人数从 i 减一推到 i,把上一档获胜者的位置加上 k、对 i 取余,余数是 0 就归到第 i 位。顺着 i 从 1 数到 7,获胜者位置依次是 1、2、2、1、4、1、4,最后 g(7) 落在 4 号,和刚才一个一个数出来的结果分毫不差。（动画第 25 步）
最优解：一步一步想明白
- 3记牢:每轮包含起点往后数 k 个,第 k 个出局,从下一位重起;把圆圈拉直成队列、数过没中的绕到队尾就等于转圈。想更快就用递推 g(i)=(g(i-1)+k)%i,余 0 归到第 i 位。
- 4先把场面摆出来。7 个小伙伴围成一圈,顺时针编号 1 到 7。我们把这个圆圈从 1 号开始拉直成一条队列来看:队首就是当前正要数的人,数到却没被淘汰的人会绕到队尾,等于回到圈里继续往下转。这一节用 n=7、k=3 走完全程。
- 5规则再点一遍:从队首开始,把队首本人算作第 1 个,往后一共数 3 个,数到的第 3 个那位离开圈子;中间没被数中的人依次绕到队尾。现在队首是 1 号,开始数第一轮。
- 6第 1 轮,从当前队首开始数。数到第 1 个,是 1 号。还没数到第 3 个,所以他这一轮安全,把他移到队伍最末尾,这一绕就相当于沿着圆圈继续往下数。
- 7第 1 轮,从当前队首开始数。数到第 2 个,是 2 号。还没数到第 3 个,所以他这一轮安全,把他移到队伍最末尾,这一绕就相当于沿着圆圈继续往下数。
- 8继续数,第 3 个正好落在 3 号身上,他就是这一轮要离开圈子的人。3 号出局,从他顺时针的下一位、也就是新队首接着数。
- 9第 2 轮,从当前队首开始数。数到第 1 个,是 4 号。还没数到第 3 个,所以他这一轮安全,把他移到队伍最末尾,这一绕就相当于沿着圆圈继续往下数。
- 10第 2 轮,从当前队首开始数。数到第 2 个,是 5 号。还没数到第 3 个,所以他这一轮安全,把他移到队伍最末尾,这一绕就相当于沿着圆圈继续往下数。
- 11继续数,第 3 个正好落在 6 号身上,他就是这一轮要离开圈子的人。6 号出局,从他顺时针的下一位、也就是新队首接着数。
- 12第 3 轮,从当前队首开始数。数到第 1 个,是 7 号。还没数到第 3 个,所以他这一轮安全,把他移到队伍最末尾,这一绕就相当于沿着圆圈继续往下数。
- 13第 3 轮,从当前队首开始数。数到第 2 个,是 1 号。还没数到第 3 个,所以他这一轮安全,把他移到队伍最末尾,这一绕就相当于沿着圆圈继续往下数。
- 14继续数,第 3 个正好落在 2 号身上,他就是这一轮要离开圈子的人。2 号出局,从他顺时针的下一位、也就是新队首接着数。
- 15第 4 轮,从当前队首开始数。数到第 1 个,是 4 号。还没数到第 3 个,所以他这一轮安全,把他移到队伍最末尾,这一绕就相当于沿着圆圈继续往下数。
- 16第 4 轮,从当前队首开始数。数到第 2 个,是 5 号。还没数到第 3 个,所以他这一轮安全,把他移到队伍最末尾,这一绕就相当于沿着圆圈继续往下数。
- 17继续数,第 3 个正好落在 7 号身上,他就是这一轮要离开圈子的人。7 号出局,从他顺时针的下一位、也就是新队首接着数。
- 18第 5 轮,从当前队首开始数。数到第 1 个,是 1 号。还没数到第 3 个,所以他这一轮安全,把他移到队伍最末尾,这一绕就相当于沿着圆圈继续往下数。
- 19第 5 轮,从当前队首开始数。数到第 2 个,是 4 号。还没数到第 3 个,所以他这一轮安全,把他移到队伍最末尾,这一绕就相当于沿着圆圈继续往下数。
- 20继续数,第 3 个正好落在 5 号身上,他就是这一轮要离开圈子的人。5 号出局,从他顺时针的下一位、也就是新队首接着数。
- 21第 6 轮,从当前队首开始数。数到第 1 个,是 1 号。还没数到第 3 个,所以他这一轮安全,把他移到队伍最末尾,这一绕就相当于沿着圆圈继续往下数。
- 22第 6 轮,从当前队首开始数。数到第 2 个,是 4 号。还没数到第 3 个,所以他这一轮安全,把他移到队伍最末尾,这一绕就相当于沿着圆圈继续往下数。
- 23继续数,第 3 个正好落在 1 号身上,他就是这一轮要离开圈子的人。1 号出局,从他顺时针的下一位、也就是新队首接着数。
- 24一路淘汰下来,出局顺序是 3、6、2、7、5、1,圈里最后只剩 4 号一个人,再没有人可淘汰,4 号就是这场游戏的获胜者,答案就是 4。
- 25换个角度验证一下。这类围圈报数有条漂亮的递推:只有 1 个人时获胜者就是 1 号;人数从 i 减一推到 i,把上一档获胜者的位置加上 k、对 i 取余,余数是 0 就归到第 i 位。顺着 i 从 1 数到 7,获胜者位置依次是 1、2、2、1、4、1、4,最后 g(7) 落在 4 号,和刚才一个一个数出来的结果分毫不差。
⚠️ 容易写错的地方
✗ 错：数 k 个时忘了把起点算进去,从起点后面才开始数第 1 个
✓ 对：把起点本人算作第 1 个,往后数到第 k 个才出局
题目明确说计数包含起始的那位。少算这一步就整体错位一位,连带最终获胜者也会算错
✗ 错：取余得到 0 时直接返回 0
✓ 对：余数为 0 代表绕完一圈正好落在最后一位,应返回 n
答案是 1 号起编的编号,合法范围是 1 到 n。取余的自然结果是 0 到 n 减 1,要把 0 翻译成第 n 位,别把不存在的 0 号返回出去
✗ 错：淘汰一个人后又回到 1 号从头数
✓ 对：从被淘汰者顺时针的下一位接着数
每一轮的起点是上一轮出局者的下一位,不是固定的 1 号。用队列模拟时,出局者一走,新的队首自动就是这个正确起点
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def findTheWinner(self, n: int, k: int) -> int:
if n == 1:
return 1
ans = (k + self.findTheWinner(n - 1, k)) % n
return n if ans == 0 else ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
int findTheWinner(int n, int k) {
if (n == 1) return 1;
int ans = (findTheWinner(n - 1, k) + k) % n;
return ans == 0 ? n : ans;
}
};Java
import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
public int findTheWinner(int n, int k) {
if (n == 1) {
return 1;
}
int ans = (findTheWinner(n - 1, k) + k) % n;
return ans == 0 ? n : ans;
}
}复杂度
时间
O(n)
参考代码的递推从 1 个人一路推到 n 个人,每推进一档只做一次加法和一次取余,都是常数操作,总共 n 档,所以时间是 O(n)。动画里那种一圈圈真数的队列模拟,每轮最多要数 k 步、一共淘汰 n 减 1 轮,是 O(n 乘 k),递推明显更快
空间
O(n)
按峰值算:参考代码是递归,从 n 一层层调用到 1,调用栈最深有 n 层,所以空间是 O(n)。这正是题目进阶想优化的点,把递推改成从小到大的循环、只用一个变量滚动更新,就能把空间压到 O(1)。动画的队列模拟另需额外存放剩余的人,也是 O(n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 找出游戏的获胜者 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么可以用递推 g(i)=(g(i-1)+k)%i 求解?+
把问题按人数从小往大想。假设已经知道 i 减 1 个人时获胜者站在哪个位置,现在多加一个人凑成 i 个人玩。新的一轮第一个出局的是第 k 个人,他走之后剩下的 i 减 1 个人重新围圈,这跟 i 减 1 个人的子问题结构完全一样,只是起点和编号整体平移了 k 位。把子问题答案的位置加上 k、对 i 取余,就换算回了当前这一圈的位置,递推就是这么一层层还原上来的。
取余结果为什么等于 0 时要返回 n?+
因为编号从 1 到 n,而取余运算给出的范围是 0 到 n 减 1。0 这个值在 1 起编的世界里并不存在,它对应的其实是绕完整整一圈正好落在最后一个,也就是第 n 位。所以代码里统一把余 0 翻译成 n,其余情况直接用余数本身。
能不能做到线性时间加常数空间?+
可以。递推本身就是 O(n) 时间。空间上,递归版本因为调用栈有 O(n) 开销;但这条递推没有分叉、是一条直线依赖,把它改成从 1 到 n 的循环,用一个变量不断滚动更新,就不再需要栈,空间降到 O(1)。这正是题目进阶想要的线性时间、常数空间解法。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 找出游戏的获胜者 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。