约瑟夫问题在O（n）使用循环列表

Question

我最近偶然发现了一个论坛，声称约瑟夫问题可以通过数据结构在O（n）中解决。这里明确的选择是一个循环链表，但我声称它只能在O（kn）或O（n^2）中完成，除非在维基百科上进行数学递归/迭代约瑟夫算法。首先，循环链表具有以下属性：搜索O（n），删除O（1），追加O（1）。假设delete是给定节点，append替换头或尾。

如果我们有节点的循环列表，我们可以发现从起点到删除节点如下：

N = 6个节点

K =删除每第三节点

起点：节点＃0

节点：0，1，2，3，4，5

我们可以计算通过第（k +起点 - 1）要删除的节点％N。对于startpoint = 0，我们有（3 + 0 - 1）％6 = 2。现在，3将是我们的出发点。 （3 + 3 - 1）％5 = 0，当移动时是我们原来的5个节点（即现在的数字将是0,1,2,3,4，因为原来的2消失了）。这基本上是数学版本的工作原理。对于一个链表，我们可以派生出哪个节点需要类似的删除。问题是我们必须前往这个节点。链接列表有O（n）搜索，这是一个问题。所以我们遍历这个节点，删除它，现在我们有n = n-1。我们找到下一个索引，做一个O（n）搜索并且有n = n_original - 2。这变成n +（n-1）+（n-2）+ ... = O（n^2）。

如果我们有一个双向链接的循环列表，那么如果节点距离我们较近，我们就不必一路绕过。如果k小于n，则这是O（k）搜索，并且O（n）搜索k是否大于n（因为在你开始之前只能移动n个节点，但是如果k很小，你只需要将k移开，并且你不会到达你开始的位置）。

无论如何，我的观点是我没有看到你如何通过O（n）中的数据结构来做到这一点。维基百科上的解决方案是O（n）中非常优雅的数学方法，它显示递归的力量（保持纯粹通过调用堆栈跟踪旧的起始点等），但是在删除实际对象时，似乎不可能得到O（ N）。我想展示自己试图弄清楚这一点，而不是公然地问，所以有人知道在O（n）中使用某种数据结构来做到这一点的方法吗？谢谢！

Answer 1

我在O（n）时间在my blog用一个循环链表解决了这个问题。该网站还使用队列和O（n^2）解决方案使用普通（非循环）链接列表提供O（n）解决方案。有了一个循环链表，你总是前进，永远不会后退，因为你建议使用双向链表。

作为一个例子，看看你的清单。你从0开始计数3删除项目3.然后计数3并删除0.然后计数3并删除4.然后计数3并删除2.然后计数3并删除5.最后计数3并删除1.总计步数是kn，其中n是节点的数量，k是步长。但是这是节点数O（n），因为n是问题的大小，k是常数。