我最近偶然发现了一个论坛，声称约瑟夫斯问题可以用数据结构在 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 + StartingPoint - 1) % n 计算要删除的节点。对于 startpoint = 0，我们有 (3 + 0 - 1) % 6 = 2。现在，3 将是我们的起点。(3 + 3 - 1) % 5 = 0，当移位时是我们原来的 5 节点（即，由于原来的 2 已经消失，数字现在将是 0,1,2,3,4）。这基本上就是数学版本的工作原理。对于链表，我们可以类似地推导出哪个节点需要删除。问题是我们必须前往这个节点。链表有 O(n) 搜索，这是一个问题。所以我们遍历这个节点，删除它，现在我们有n = n-1。我们找到下一个索引，进行 O(n) 搜索，得到 n = n_original - 2。这变为 n + (n-1) + (n-2) + ... = O(n^2)。
如果我们有一个双向循环列表，那么如果节点离我们后面更近，我们就不必一路走来走去。尽管如此，如果 k 小于 n，这仍然是 O(k) 搜索，如果 k 大于 n，则搜索 O(n)你只需要把 k 移开，你就不会到达你开始的地方）。
无论如何，我的观点是我看不出你如何通过 O(n) 中的数据结构来做到这一点。维基百科上的解决方案是 O(n) 中非常优雅的数学方法，它显示了递归的力量（纯粹通过调用堆栈来跟踪旧起点等），但是当删除实际对象时似乎不可能得到 O( n)。我想展示我试图解决这个问题的尝试，而不仅仅是公然问，那么有没有人知道在 O(n) 中使用一些数据结构来做到这一点的方法？谢谢！