最后剩余的号码

Question

采访中有人问我这个问题。

给定一个正整数数组“ arr”和该数组的起始索引“ k”。删除k处的元素，并以循环方式在数组中跳过arr [k]步骤。重复执行此操作，直到仅剩一个元素。找到最后剩余的元素。

我想到了使用有序映射的O（nlogn）解决方案。是否有任何O（n）解决方案？

Answer 1

我想不出解决O(n)办法。然而，我们可以O(n log n)通过使用 treap 或增强的 BST 来获得平均时间，每个节点都有一个值作为其子树的大小。陷阱使我们能够找到并删除k在平均时间内找到并删除第 th 个条目O(log n)。

例如，A = [1, 2, 3, 4]并且k = 3（正如 Sumit 在评论中提醒我的那样，使用数组索引作为树中的值，因为它们是有序的）：

          2(0.9)
         /     \
      1(0.81)   4(0.82)
               /
              3(0.76)

找到并删除第三个元素。从 2 开始，大小 = 2（包括左子树）。向右走。左子树的大小为 1，合起来为 3，因此我们找到了第 3 个元素。消除：

          2(0.9)
         /     \
      1(0.81)   4(0.82)

现在，我们从包含元素的数组中的第三个元素开始n - 1 = 3，并从那里查找第三个元素。我们将使用零索引与我们的模算术相关联，因此模数 3 中的第三个元素将是 2 并且2 + 3 = 5 mod 3 = 2第二个元素是 。我们立即找到它，因为其左子树的根大小为 2。删除：

          4(0.82)
         /
      1(0.81)

现在我们从模 2 的第二个元素开始，即 1，然后添加 2。3 mod 2 为 1。删除第一个元素，剩下 4 作为最后一个元素。