algorithm - 最后剩余号码

Question

我在面试中被问到这个问题。

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

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

Answer 1

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

1. O(1) 从数据结构中进行保序删除。
2. O(1) 查找数据结构中第 n 个未删除的项目。

但是，这样的数据结构已经被正式证明不存在；请参阅“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) 算法——例如, 只是使用循环链表。