O(nlgn)的Josephus环解法

Josephus问题的定义如下：假设n个人排成环形，且有一正整数m<=n。从某个指定的人开始，沿环报数。每遇到第m个人就让其出列，且报数进行下去，这个过程直到所有人都出列为止。假设m不是常数。请描述一个O(nlgn)时间的算法，使给定的整数n和m，输出(n,m)-Josephus排列。

 

解法：使用顺序统计树(order-statistic tree)，顺序统计树的插入、删除的时间复杂度为O(lgn)，查找第i大的数的时间复杂度也为O(lgn)。

 

伪代码：

 

JOSEPHUS(n,m)

initialize T to be empty

1. for j ← 1 to n

do create a node x with key[x] = j

OS-INSERT(T, x)

 

k ← n

j ← m

 

2.while k > 2

do x ← OS-SELECT(root[T ], j )

print key[x]

OS-DELETE(T, x)

k ← k − 1

j ← (( j + m − 2) mod k) + 1

 

3.print key[OS-SELECT(root[T ], 1)]

 

1.建立顺序统计树

2.先找出第j=m大的数，打印，然后从顺序统计数中将其删除，则下一个要删除的数为此时序列中第j+m-1大的数(序列的长度已经减小了1，所以是j+m-1而不是j+m)，因为j+m-1可能大于n，所以写成 ((j+m-2)mod k) + 1

3.打印最后一个数