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

Question

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

在更具体的情况下，如果数组由所有 0 值初始化，并且始终仅通过将索引的值增加 1 来增量构造，是否存在 O(1) 解决方案？

原文由 Farshid 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

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

但是假设您维护我提到的数据结构（地图可以工作，因为它具有 O(1) 查找）。在这种情况下，你会有这样的事情：

 0 -> 3

因此，您有一系列 0 值在 3 位置结束。当您增加一个值时，假设在位置 i ，您检查新值是否大于 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 。这意味着您可以将当前位置的值与索引 4 处的值交换：

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

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

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

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

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

请随意戳洞。

更新

我 在这里 用 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] + ")";
        }
    }
}

原文由 Vivin Paliath 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

在更具体的情况下，如果数组由所有 0 值初始化，并且始终仅通过将索引的值增加 1 来增量构造，是否存在 O(1) 解决方案？

不。给定一个全 0 的数组： [0, 0, 0, 0, 0] 。如果您增加第一个值，给出 [1, 0, 0, 0, 0] ，那么您必须进行 4 次交换以确保它保持排序。

给定一个没有重复的排序数组，那么答案是肯定的。但是在第一次操作之后（即第一次递增），您可能会有重复项。您执行的增量越多，重复的可能性就越高，并且越有可能花费 O(n) 来保持该数组的排序。

如果您只有数组，则不可能保证每次增量少于 O(n) 时间。如果您正在寻找的是支持排序顺序和按索引查找的数据结构，那么您可能需要一个 顺序静态树。

原文由 Jim Mischel 发布，翻译遵循 CC BY-SA 3.0 许可协议