Leetcode1823:找出游戏的获胜者——约瑟夫环

题目

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

约瑟夫环问题非常经典，记得大一学c++程序设计的时候遇到过这题，当时貌似没有做出来，现在就游刃有余了。

题解

朴素的模拟法

即真正按照题目的描述，维护一个初始长度为n的数组和计数变量cnt，迭代找到最终解。最朴素的方法，一般都会超时。

模拟+队列

使用队列来模拟这个过程，首先创建一个双端队列（python中有此数据结构），包括n个数。然后在接下来的n-1次迭代中每次从队首pop出k-1个数到队尾。最终剩下的数就是答案。

class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        q = deque(range(1, n + 1))
        while len(q) > 1:
            for _ in range(k - 1):
                q.append(q.popleft())
            q.popleft()
        return q[0]

因为要执行n-1轮，每轮把k-1个数从队首拿到队尾，所以时间复杂度为O(nk)。和第一种方法差不多，但代码更简洁。

直接pop

对上面的方法进行优化，也是我采用的方法。就是在每轮迭代中省去计数这个过程，直接找到要pop的数。

class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        people = [i for i in range(1,n+1)]
        kick = 1
        while(len(people)!=1):
            kick = (kick-1+k)%len(people)
            if kick==0:kick=len(people)
            people.pop(kick-1)
            print(kick,end=" ")
            print(people)
        return people[0]

细节：

• 记录上一次杀掉的人的位置为kick（从1开始计数），那么下一次从第kick人开始计k个数，它的位置是kick+k-1。
• 但考虑到是一个环，所以要把位置mod当前数组的长度。
• mod时有一个问题，如果位置恰好是最后一个元素，mod结果为0，所以加一个判断条件，如果结果为0，就令它等于len(people)。
• 因为我们分析的位置是从1开始计数，所以pop的时候要-1

由于pop的时间复杂度比较高，所以这也不是一种十分优雅的方法。

数学+递归/数学+迭代

递归公式

f(n,m)=(f(n-1,m)+m)%n
f(n,m)指n个人，报第m个编号出列最终编号

这个推理没搞懂…题解：https://leetcode-cn.com/circle/article/BOoxAL/

时间复杂度O(n)