3.约瑟夫环

问题描述

约瑟夫环问题是这样的：

0,1,…,n−1 这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

解题思路

从后往前依次推导，

最后只剩下1个数字，它在位置pos=0。

倒数第二轮，只剩下2个数字，最后剩下的数字的位置pos=(0+m)%2

倒数第三轮，只剩下3个数字，最后剩下的数字的位置pos=((0+m)%2+m)%3

......

这样第一轮它所在的位置就能推导出来，就是我们要求的。

(数学证明略)

class Solution(object):
    def findTheNumber(self, n, m):
        pos = 0
        for i in range(2,n+1):
            pos = (pos + m) % i
        return pos

例题

力扣1823

# 1.使用数学迭代，就是上面的那个模板 
# 时间O(n) 空间O(1)
class Solution(object):
    def findTheWinner(self, n, k):
        pos = 0
        for i in range(2, n + 1):
            pos = (pos + k) % i
        return pos + 1

# 2.使用队列
# 时间O(nk) 空间O(n)
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]

# 3.本人一时脑热的集合版本
class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        index=0
        a=[]
        a=set(a)
        for i in range(n):
            a.add(i+1)
        i=1
        while i<=n:
            if len(a)==1:
                a=list(a)
                return a[0]
            if i in a:
                index+=1
            if(index==k):
                a.remove(i)
                index=0
            i+=1
            i=i%(n+1)
            if(i==0):
                i=1