c++ - 在 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)。

但是假设您维护我提到的数据结构( map 可以工作，因为它具有 O(1) 查找)。在这种情况下，你会得到这样的东西:

0 -> 3

所以你有一个 0 值在位置 3 结束。当您增加一个值时，例如在位置 i 处，您检查新值是否大于 i + 1 处的值。如果不是，那你很好。但如果是，则查看辅助数据结构中是否有此值的条目。如果没有，您可以简单地交换。如果有 条目，则查找结束索引，然后与该位置的值交换。然后，您需要对辅助数据结构进行任何更改以反射(reflect)数组的新状态。

一个更详尽的例子:

[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，这意味着有一个运行在4 处的3。这意味着您可以将当前位置的值与索引 4 处的值交换:

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

现在您还需要更新辅助数据结构。具体来说，3 的运行提前结束了一个索引，因此您需要减少该值:

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

您需要做的另一项检查是查看该值是否已重复。您可以通过查看 i - 1th 和 i + 1th 位置来检查它们是否与相关值相同。如果两者都不相等，那么您可以从映射中删除该值的条目。

同样，这只是一个一般性的想法。我将不得不对其进行编码，以查看它是否按我的想法工作。

请随意戳洞。

更新

我有这个算法的实现 here在 JavaScript 中。我使用 JavaScript 只是为了快速完成。另外，因为我很快就编写好了它，所以它可能会被清理掉。不过我确实有意见。我也没有做任何深奥的事情，所以这应该很容易移植到 C++。

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

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

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] + ")";
        }
    }
}