最后剩下的号码

Question

我在一次采访中被问到这个问题。

给定正整数数组“arr”和数组的起始索引“k”。删除k处的元素，并以循环方式在数组中跳转arr[k]步。重复这样做，直到只剩下一个元素。找到最后剩下的元素。

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

Answer 1

我想不出O（n）解决方案。但是，我们可以通过使用 treap 或增强的 BST 来获得 O（n log n） 平均时间，每个节点中都有一个值来表示其子树的大小。treap 使我们能够找到并删除 O（log n） 平均时间中的第 k个条目。

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

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

查找并删除第三个元素。从2开始，大小为2（包括左子树）。向右走。左子树的大小为1，加起来等于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模2等于1。除去第一个元素，我们剩下4作为最后一个元素。

Answer 2

我的猜测是，这个问题没有< code>O(n)的解决方案，因为它似乎涉及到做一些不可能的事情。要在线性时间内解决这个问题，显然需要一个像数组这样的数据结构，它公开了对值的有序集合的两个操作:

< li> O(1)按顺序从数据结构中删除。 在数据结构中查找第n个未删除的项目。

然而，这样的数据结构已经被正式证明是不存在的；参见“列表索引和子集排名的最佳算法”及其引用。说如果解决某个问题的自然方式涉及使用不可能的数据结构，问题本身很可能是不可能的，这并不是一个证明，但这样的直觉往往是正确的。

无论如何，在O（n log n）中有很多方法可以做到这一点。下面是在数组中维护未删除范围树的实现。下面的GetIndex（）返回原始数组的索引，如果项目已被删除，则给定数组中从零开始的索引。这样的树不是自平衡的，因此在最坏的情况下会有O（n）操作，但在一般情况下Delete和GetIndex将是O（log n）。

namespace CircleGame
{
    class Program
    {
        class ArrayDeletes
        {
            private class UndeletedRange
            {
                private int _size;
                private int _index;
                private UndeletedRange _left;
                private UndeletedRange _right;

                public UndeletedRange(int i, int sz)
                {
                    _index = i;
                    _size = sz;
                }

                public bool IsLeaf()
                {
                    return _left == null && _right == null;
                }

                public int Size()
                {
                    return _size;
                }

                public void Delete(int i)
                {
                    if (i >= _size)
                        throw new IndexOutOfRangeException();

                    if (! IsLeaf())
                    {
                        int left_range = _left._size;
                        if (i < left_range)
                            _left.Delete(i);
                        else
                            _right.Delete(i - left_range);
                        _size--;
                        return;
                    }

                    if (i == _size - 1)
                    {
                        _size--; // Can delete the last item in a range by decremnting its size
                        return;
                    }

                    if (i == 0)  // Can delete the first item in a range by incrementing the index
                    {  
                        _index++;
                        _size--;
                        return;
                    }

                    _left = new UndeletedRange(_index, i);
                    int right_index = i + 1;
                    _right = new UndeletedRange(_index + right_index, _size - right_index);
                    _size--;
                    _index = -1; // the index field of a non-leaf is no longer necessarily valid.
                }

                public int GetIndex(int i)
                {
                    if (i >= _size)
                        throw new IndexOutOfRangeException();

                    if (IsLeaf())
                        return _index + i;

                    int left_range = _left._size;
                    if (i < left_range)
                        return _left.GetIndex(i);
                    else
                        return _right.GetIndex(i - left_range);
                }

            }

            private UndeletedRange _root;

            public ArrayDeletes(int n)
            {
                _root = new UndeletedRange(0, n);
            }

            public void Delete(int i)
            {
                _root.Delete(i);
            }

            public int GetIndex(int indexRelativeToDeletes )
            {
                return _root.GetIndex(indexRelativeToDeletes);
            }

            public int Size()
            {
                return _root.Size();
            }
        }

        static int CircleGame( int[] array, int k )
        {
            var ary_deletes = new ArrayDeletes(array.Length);
            while (ary_deletes.Size() > 1)
            {
                int next_step = array[ary_deletes.GetIndex(k)];
                ary_deletes.Delete(k);
                k = (k + next_step - 1) % ary_deletes.Size();
            }
            return array[ary_deletes.GetIndex(0)];
        }

        static void Main(string[] args)
        {
            var array = new int[] { 5,4,3,2,1 };
            int last_remaining = CircleGame(array, 2); // third element, this call is zero-based...
        }
    }
}

另请注意，如果数组中的值已知有界，因此它们总是小于m小于n，则有许多O（nm）算法——例如，仅使用循环链表。