在O(1)中维护一个排序数组？

Question

我们有一个排序数组,我们希望将一个索引的值增加1个单位(array [i] ++),这样生成的数组仍然是排序的.这可能在O(1)中吗？可以在STL和C++中使用任何可能的数据结构.

在一个更具体的情况下,如果数组是由所有0值初始化的,并且它总是仅通过将索引值增加1来递增构造,那么是否存在O(1)解？

Answer 1

我没有完全解决这个问题,但我认为总体思路至少对整数有帮助.以更多内存为代价,您可以维护一个单独的数据结构,该结构维护一系列重复值的结束索引(因为您希望将递增的值与重复值的结束索引进行交换).这是因为重复的值会导致您遇到最坏情况的O(n)运行时:假设您已经[0, 0, 0, 0]并且在位置增加了值0.然后是O(n)找出最后一个位置(3).

但是,让我们说你维护我提到的数据结构(地图可以工作,因为它有O(1)查找).在这种情况下你会有这样的事情:

0 -> 3

因此,您有一系列0以位置结束的值3.当你增加一个值时,让我们说在位置i,你检查新值是否大于at值i + 1.如果不是,你很好.但如果是,则查看辅助数据结构中是否存在此值的条目.如果没有,你可以简单地交换.如果是一个条目,你查查结束索引,然后在该位置的价值交换.然后,您需要对辅助数据结构进行任何更改,以反映阵列的新状态.

一个更彻底的例子:

[0, 2, 3, 3, 3, 4, 4, 5, 5, 5, 7]

辅助数据结构是:

3 -> 4
4 -> 6
5 -> 9

假设您在位置增加值2.所以你增加了3,到4.该数组现在看起来像这样:

[0, 2, 4, 3, 3, 4, 4, 5, 5, 5, 7]

你看下一个元素,就是3.然后,在辅助数据结构中查找该元素的条目.条目是4,这意味着有一系列3的结束4.这意味着您可以将当前位置的值与index处的值进行交换4:

[0, 2, 3, 3, 4, 4, 4, 5, 5, 5, 7]

现在,您还需要更新辅助数据结构.具体来说,运行时3会提前结束一个索引,因此您需要递减该值:

3 -> 3
4 -> 6
5 -> 9

您需要做的另一项检查是查看该值是否重复.您可以通过查看位置i - 1和i + 1位置来检查它们是否与相关值相同.如果两者不相等,则可以从地图中删除此值的条目.

同样,这只是一个普遍的想法.我将不得不编写它以查看它是否按照我的想法运行.

请随意戳破洞.

UPDATE

我在这里用JavaScript 实现了这个算法.我只使用JavaScript,所以我可以快速完成.此外,因为我很快编码它可能会被清理干净.我确实有评论.我也没有做任何深奥的事情,所以这应该很容易移植到C++.

该算法基本上有两个部分:递增和交换(如果需要),以及在地图上完成的簿记,用于跟踪重复值运行的结束索引.

该代码包含一个测试工具,它以零数组开头并递增随机位置.在每次迭代结束时,都会进行测试以确保对数组进行排序.

var array = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
var endingIndices = {0: 9};

var increments = 10000;

for(var i = 0; i < increments; i++) {
    var index = Math.floor(Math.random() * array.length);    

    var oldValue = array[index];
    var newValue = ++array[index];

    if(index == (array.length - 1)) {
        //Incremented element is the last element.
        //We don't need to swap, but we need to see if we modified a run (if one exists)
        if(endingIndices[oldValue]) {
            endingIndices[oldValue]--;
        }
    } else if(index >= 0) {
        //Incremented element is not the last element; it is in the middle of
        //the array, possibly even the first element

        var nextIndexValue = array[index + 1];
        if(newValue === nextIndexValue) {
            //If the new value is the same as the next value, we don't need to swap anything. But
            //we are doing some book-keeping later with the endingIndices map. That code requires
            //the ending index (i.e., where we moved the incremented value to). Since we didn't
            //move it anywhere, the endingIndex is simply the index of the incremented element.
            endingIndex = index;
        } else if(newValue > nextIndexValue) {
            //If the new value is greater than the next value, we will have to swap it

            var swapIndex = -1;
            if(!endingIndices[nextIndexValue]) {
                //If the next value doesn't have a run, then location we have to swap with
                //is just the next index
                swapIndex = index + 1;
            } else {
                //If the next value has a run, we get the swap index from the map
                swapIndex = endingIndices[nextIndexValue];
            }

            array[index] = nextIndexValue;
            array[swapIndex] = newValue;

            endingIndex = swapIndex;

        } else {
        //If the next value is already greater, there is nothing we need to swap but we do
        //need to do some book-keeping with the endingIndices map later, because it is
        //possible that we modified a run (the value might be the same as the value that
        //came before it). Since we don't have anything to swap, the endingIndex is 
        //effectively the index that we are incrementing.
            endingIndex = index;
        }

        //Moving the new value to its new position may have created a new run, so we need to
        //check for that. This will only happen if the new position is not at the end of
        //the array, and the new value does not have an entry in the map, and the value
        //at the position after the new position is the same as the new value
        if(endingIndex < (array.length - 1) &&
           !endingIndices[newValue] &&
           array[endingIndex + 1] == newValue) {
            endingIndices[newValue] = endingIndex + 1;
        }

        //We also need to check to see if the old value had an entry in the
        //map because now that run has been shortened by one.
        if(endingIndices[oldValue]) {
            var newEndingIndex = --endingIndices[oldValue];

            if(newEndingIndex == 0 ||
               (newEndingIndex > 0 && array[newEndingIndex - 1] != oldValue)) {
                //In this case we check to see if the old value only has one entry, in
                //which case there is no run of values and so we will need to remove
                //its entry from the map. This happens when the new ending-index for this
                //value is the first location (0) or if the location before the new
                //ending-index doesn't contain the old value.
                delete endingIndices[oldValue];
            }
        }
    }

    //Make sure that the array is sorted   
    for(var j = 0; j < array.length - 1; j++) {
        if(array[j] > array[j + 1]) {        
            throw "Array not sorted; Value at location " + j + "(" + array[j] + ") is greater than value at location " + (j + 1) + "(" + array[j + 1] + ")";
        }
    }
}

Answer 2

在一个更具体的情况下,如果数组是由所有0值初始化的,并且它总是仅通过将索引值增加1来递增构造,那么是否存在O(1)解？

不,给出一个全0的数组:[0, 0, 0, 0, 0].如果递增第一个值,则给出[1, 0, 0, 0, 0],然后您将必须进行4次交换以确保它保持排序.

给定一个没有重复的排序数组,答案是肯定的.但是在第一次操作之后(即第一次增加),你可能会有重复.您执行的增量越多,您重复的可能性就越高,O(n)保持该数组排序的可能性就越大.

如果您只拥有数组,则无法保证每个增量的时间少于O(n).如果您正在寻找的是支持排序顺序和按索引查找的数据结构,那么您可能需要一个订单stastic树.