算法-如何优化约瑟夫问题的效率

Question

有一组数字排成一圈，按1、2、3、4……n依次排号，然后从第一个开始数，数到第m的时候，把这个数剔除，从它后面再开始数，再数到m的时候，把它剔除，如此循环下去，直到最后剩余一个数。 求解最后剩的这个数？
以上问题是一个约瑟夫问题，通常的做法是模拟描述中的过程，但是 时间复杂度高达O(nm），如果n和m都相当大，那么在短时间内找到最后剩下的一个数字是不容易的。如何优化常规算法，使其时间复杂度为 O(n) ?

Answer 1

这是典型的约瑟夫问题，代码就不贴了。约瑟夫问题 PHP