面试题

某大厂迎来了新入职的大学生，现在需要为每个新同事分配一个工号。

人力资源部同事设计了一个方法为每个人进行排序并分配最终的工号，具体规则是：

将N（N<10000）个人排成一排，从第1个人开始报数；如果报数是M的倍数就出列，报到队尾（最后一位），则从头（回到对头）继续报，直到所有人都出列；最后按照出列顺序为每个人依次分配工号

 

思考

先出列，即将原数组中的该数字删除，先循环每位上的数字，可以和M除的尽，则出列；

如何维护原数列呢？若采用删除的办法，数列的长度会变，这样循环位置就不可以了，苦思冥想半天，无果；百度，维护原数列，采用切片的方式，终于ok；

先出列

假设10个人，报道3的倍数就出列

l=list(range(1,11))
n=3
newl=[]
while len(l)>=n:
    newl.append(l[n-1])
    l=l[n:]+l[:n-1]
print(l) #多余的
print(newl) #新数列

　运行结果：

[10, 4]
[3, 6, 9, 2, 7, 1, 8, 5]

 最后还剩2个人将继续报数；

人数小于n的情况

先循环[10,4]，继续循环[10,4]，此时10出列，剩余4；　

思考：所以当时采用减法，3-2=1，所以直接取列表的第1位；

           后面发现，若是剩余4位，取10的倍数，此方法就不可行，最后改为取余数；

l=list(range(1,11))
n=3
newl=[]
while len(l)>=n:
    newl.append(l[n-1])
    l=l[n:]+l[:n-1]
print(l) #多余的
print(newl) #新数列

while len(l)>1:#因为前面已经知道未分配的<out，不过为了保险起见，可以加上<的条件；
    a=n-len(l)
    newl.append(l[a-1])
    l=l[a:]+l[:a-1]
print(newl)
print(newl+l)

 练习：20个人，5的倍数出列

l=list(range(1,21))
newl=[]
out=5

while len(l)>=out:
    newl.append(l[out-1])
    l=l[out:]+l[:out-1] #切片左包，右不包
print(l) #剩余未被分配的
#print(newl) #新的排序

while len(l)>1:
    p=out%len(l)
    newl.append(l[p-1])
    l=l[p:]+l[:p-1]
print(l) #此时还剩余1个为分配
#print(newl) #新的排序
print(newl+l)#终极排序

 运行结果

[2, 7, 8, 14]
[7]
[5, 10, 15, 20, 6, 12, 18, 4, 13, 1, 9, 19, 11, 3, 17, 16, 2, 8, 14, 7]