题目描述
blablabla
样例
blablabla
算法1
单链表
blablabla
时间复杂度
参考文献
Python 代码
class Solution(object):
def lastRemaining(self, n, m):
"""
:type n: int
:type m: int
:rtype: int
"""
N=4005
e=[0]*N
ne=[0]*N
idx=0
head=-1
def add_to_head(x):
nonlocal idx,e,ne,head
e[idx]=x
ne[idx]=head
head=idx
idx+=1
def add(k,x):
nonlocal idx,e,ne
e[idx]=x
ne[idx]=ne[k]
ne[k]=idx
idx+=1
def remove(k):
nonlocal idx,e,ne
ne[k]=ne[ne[k]]
add_to_head(0)
k=0
for i in range(1,n):
add(k,i)
k+=1
ne[idx-1]=head
i=head
j=0
while ne[i]!=i:
j+=1
if j==m-1:
remove(i)
j=0
i=ne[i]
return e[i]
算法2
双链表
blablabla
时间复杂度
参考文献
Python 代码
class Solution(object):
def lastRemaining(self, n, m):
"""
:type n: int
:type m: int
:rtype: int
"""
N=4005
e=[0]*N
l=[0]*N
r=[0]*N
idx=2
r[0]=1
l[1]=0
def add(k,x):
nonlocal idx
e[idx]=x
r[idx]=r[k]
l[idx]=k
r[k]=idx
l[r[idx]]=idx
idx+=1
def remove(k):
r[l[k]]=r[k]
l[r[k]]=l[k]
add(0,0)
j=r[0]
for i in range(1,n):
add(j,i)
j=r[j]
r[idx-1]=r[0]
l[r[0]]=idx-1
i=r[0]
k=0
while r[i]!=i:
k+=1
if k==m-1:
k=0
remove(r[i])
i=r[i]
return e[i]