leetcode 面试题62. 圆圈中最后剩下的数字 约瑟夫环问题 数学反推

leetcode 2020年3月 每日一题打卡
剑指offer

题目：
0,1,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

示例 1：输入: n = 5, m = 3 输出: 3
示例 2：输入: n = 10, m = 17 输出: 2
限制：
1 <= n <= 10^5
1 <= m <= 10^6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof

思路： 数学题，约瑟夫环问题。用循环链表的复杂度是O(nm)，超时。看题解才知道这是个有名的数学题。数学解的方法是反推，反推的过程是 (当前index + m) % 上一轮剩余数字的个数。时间复杂度O(n)。下面约瑟夫环问题的解法摘自甜姨的题解。【Respect甜姨】

代码：

class Solution(object):def lastRemaining(self, n, m):""":type n: int:type m: int:rtype: int"""sit=0for i in range(2,n+1):sit=(sit+m)%ireturn sit

用循环链表的超时代码：

class Node(object):def __init__(self,value):self.value=valueself.next=Noneclass LinkNode(object):def __init__(self,node):#链表建立时必须有一个节点self.head=nodenode.next=self.head #循环self.length=1'''def length(self):count=1cur=self.__headwhile cur.next != self.__head:count+=1return count'''def TailInsert(self,num):node=Node(num)cur=self.headwhile cur.next != self.head:cur=cur.nextcur.next=nodecur.next.next=self.headself.length+=1def Delete(self,num):prenode=self.headwhile prenode.next.value!=num:prenode=prenode.nextif prenode.next==self.head:self.head=self.head.nextprenode.next=self.headelse:prenode.next=prenode.next.nextself.length-=1class Solution(object):def lastRemaining(self, n, m):""":type n: int:type m: int:rtype: int"""link=LinkNode(Node(0))# 单向循环链表for i in range(1,n):link.TailInsert(i)curr=link.headwhile link.length !=1:for k in range(m-1):curr=curr.nexttemp=curr.nextlink.Delete(curr.value)curr=tempprint(curr.value)return link.head.value

经验是如果 n<10^5 ，那么 O(n^2) 的解法耗时大概是几秒左右（当然时间复杂度会忽略常数，而且也有可能由于执行程序的机器性能的不同， O(n^2) 的实际耗时也有可能一秒多，也有可能十几秒）。本题由于 1 <= m <= 10^6，所以 O(nm)肯定是超时的。