最后剩余号码

我的猜测是 O(n) 这个问题的解决办法是基于这样一个事实:它似乎涉及到做一些不可能的事情。要在线性时间内解决此问题,显然需要一个数据结构(如数组),它在值的有序集合上公开两个操作:

1. O(1)
2. O(一)

然而,这种数据结构已被正式证明不存在; Optimal Algorithms for List Indexing and Subset Rank

无论如何,有很多方法可以做到这一点 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) 算法——例如,只使用循环链表。

我想不出 O(n) O(n log n) 使用treap或扩展BST的平均时间,在每个节点中为其子树的大小指定一个值。treap使我们能够找到并删除 k 第项进入 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模式2是1。移除第一个元素,剩下4个元素作为最后一个元素。