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

Question

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

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

Answer 1

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

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

0 -> 3

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

一个更彻底的例子：

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

二级数据结构是：

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

假设您增加 location 的值2。所以你增加3了 , 到4。数组现在看起来像这样：

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

您查看下一个元素，即3. 然后，您在辅助数据结构中查找该元素的条目。条目是4，这意味着有一连串的3's 结束于4。这意味着您可以将当前位置的值与 index 处的值交换4：

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

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

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

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

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

请随意戳洞。

更新

我在这里用 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) 时间。如果您正在寻找的是支持排序顺序和按索引查找的数据结构，那么您可能需要一个顺序静态树。

Answer 3

如果值很小，计数排序将起作用。将数组表示[0,0,0,0]为{4}。增加任何零给出{3,1}：3个零和一个1。通常，要增加任何值 x，请从 x 的计数中减去 1 并增加 {x+1} 的计数。但是，空间效率为 O(N)，其中 N 是最大值。

Answer 4

所以你需要排序数组和哈希表。您遍历数组以找出“平坦”区域 - 其中元素具有相同的值。对于每个平坦区域，您必须弄清楚三件事 1）它从哪里开始（第一个元素的索引） 2）它的值是什么 3）下一个元素的值是什么（下一个更大的）。然后将此元组放入哈希表中，其中键将是元素值。这是先决条件，它的复杂性并不重要。

然后，当您增加某个元素（索引 i）时，您会查找一个表以查找下一个更大元素的索引（称为 j），并i与i - 1. 然后 1) 将新条目添加到哈希表 2) 更新现有条目的先前值。

使用完美的哈希表（或有限的可能值范围），它几乎是 O(1)。缺点：它不会很稳定。

这是一些代码：

#include <iostream>
#include <unordered_map>
#include <vector>

struct Range {
    int start, value, next;
};

void print_ht(std::unordered_map<int, Range>& ht)
{
    for (auto i = ht.begin(); i != ht.end(); i++) {
        Range& r = (*i).second;
        std::cout << '(' << r.start << ", "<< r.value << ", "<< r.next << ") ";
    }
    std::cout << std::endl;
}

void increment_el(int i, std::vector<int>& array, std::unordered_map<int, Range>& ht)
{
    int val = array[i];
    array[i]++;
    //Pick next bigger element
    Range& r = ht[val];
    //Do the swapping, so last element of that range will be first
    std::swap(array[i], array[ht[r.next].start - 1]);
    //Update hashtable
    ht[r.next].start--;
}

int main(int argc, const char * argv[])
{
    std::vector<int> array = {1, 1, 1, 2, 2, 3};
    std::unordered_map<int, Range> ht;

    int start = 0;
    int value = array[0];

    //Build indexing hashtable
    for (int i = 0; i <= array.size(); i++) {
        int cur_value = i < array.size() ? array[i] : -1;
        if (cur_value > value || i == array.size()) {
            ht[value] = {start, value, cur_value};
            start = i;
            value = cur_value;
        }
    }

    print_ht(ht);

    //Now let's increment first element
    increment_el(0, array, ht);
    print_ht(ht);
    increment_el(3, array, ht);
    print_ht(ht);

    for (auto i = array.begin(); i != array.end(); i++)
        std::cout << *i << " ";


    return 0;
}

Answer 5

这取决于有多少项目可以具有相同的值。如果更多项可以具有相同的值，那么普通数组不可能有 O(1)。

举个例子：假设array[5] = 21，你想做array[5]++：

• 增加项目：

  array[5]++
  

  （这是 O(1)，因为它是一个数组）。

  所以，现在数组 [5] = 22。

• 检查下一项（即数组[6]）：

  如果 array[6] == 21，那么您必须不断检查新项目（即 array[7] 等），直到找到高于 21 的值。此时您可以交换值。此搜索不是O(1)，因为您可能必须扫描整个数组。

相反，如果项目不能具有相同的值，那么您有：

• 增加项目：

  array[5]++
  

  （这是 O(1)，因为它是一个数组）。

  所以，现在数组 [5] = 22。

• 下一项不能是 21（因为两项不能有相同的值），所以它的值必须 > 21 并且数组已经排序。

Answer 6

我认为不使用哈希表是可能的。我在这里有一个实现：

#include <cstdio>
#include <vector>
#include <cassert>

// This code is a solution for http://stackoverflow.com/questions/19957753/maintain-a-sorted-array-in-o1
//
// """We have a sorted array and we would like to increase the value of one index by only 1 unit
//    (array[i]++), such that the resulting array is still sorted. Is this possible in O(1)?"""


// The obvious implementation, which has O(n) worst case increment.
class LinearIncrementor
{
public:
    LinearIncrementor(int numElems);
    int valueAt(int index) const;
    void incrementAt(int index);
private:
    std::vector<int> m_values;
};

// Free list to store runs of same values
class RunList
{
public:
    struct Run
    {
        int m_end;   // end index of run, inclusive, or next object in free list
        int m_value; // value at this run
    };

    RunList();
    int allocateRun(int endIndex, int value);
    void freeRun(int index);
    Run& runAt(int index);
    const Run& runAt(int index) const;
private:
    std::vector<Run> m_runs;
    int m_firstFree;
};

// More optimal implementation, which increments in O(1) time
class ConstantIncrementor
{
public:
    ConstantIncrementor(int numElems);
    int valueAt(int index) const;
    void incrementAt(int index);
private:
    std::vector<int> m_runIndices;
    RunList m_runs;
};

LinearIncrementor::LinearIncrementor(int numElems)
    : m_values(numElems, 0)
{
}

int LinearIncrementor::valueAt(int index) const
{
    return m_values[index];
}

void LinearIncrementor::incrementAt(int index)
{
    const int n = static_cast<int>(m_values.size());
    const int value = m_values[index];
    while (index+1 < n && value == m_values[index+1])
        ++index;
    ++m_values[index];
}

RunList::RunList() : m_firstFree(-1)
{
}

int RunList::allocateRun(int endIndex, int value)
{
    int runIndex = -1;
    if (m_firstFree == -1)
    {
        runIndex = static_cast<int>(m_runs.size());
        m_runs.resize(runIndex + 1);
    }
    else
    {
        runIndex = m_firstFree;
        m_firstFree = m_runs[runIndex].m_end;
    }
    Run& run = m_runs[runIndex];
    run.m_end = endIndex;
    run.m_value = value;
    return runIndex;
}

void RunList::freeRun(int index)
{
    m_runs[index].m_end = m_firstFree;
    m_firstFree = index;
}

RunList::Run& RunList::runAt(int index)
{
    return m_runs[index];
}

const RunList::Run& RunList::runAt(int index) const
{
    return m_runs[index];
}

ConstantIncrementor::ConstantIncrementor(int numElems) : m_runIndices(numElems, 0)
{
    const int runIndex = m_runs.allocateRun(numElems-1, 0);
    assert(runIndex == 0);
}

int ConstantIncrementor::valueAt(int index) const
{
    return m_runs.runAt(m_runIndices[index]).m_value;
}

void ConstantIncrementor::incrementAt(int index)
{
    const int numElems = static_cast<int>(m_runIndices.size());

    const int curRunIndex = m_runIndices[index];
    RunList::Run& curRun = m_runs.runAt(curRunIndex);
    index = curRun.m_end;
    const bool freeCurRun = index == 0 || m_runIndices[index-1] != curRunIndex;

    RunList::Run* runToMerge = NULL;
    int runToMergeIndex = -1;
    if (curRun.m_end+1 < numElems)
    {
        const int nextRunIndex = m_runIndices[curRun.m_end+1];
        RunList::Run& nextRun = m_runs.runAt(nextRunIndex);
        if (curRun.m_value+1 == nextRun.m_value)
        {
            runToMerge = &nextRun;
            runToMergeIndex = nextRunIndex;
        }
    }

    if (freeCurRun && !runToMerge) // then free and allocate at the same time
    {
        ++curRun.m_value;
    }
    else
    {
        if (freeCurRun)
        {
            m_runs.freeRun(curRunIndex);
        }
        else
        {
            --curRun.m_end;
        }

        if (runToMerge)
        {
            m_runIndices[index] = runToMergeIndex;
        }
        else
        {
            m_runIndices[index] = m_runs.allocateRun(index, curRun.m_value+1);
        }
    }
}

int main(int argc, char* argv[])
{
    const int numElems = 100;
    const int numInc = 1000000;

    LinearIncrementor linearInc(numElems);
    ConstantIncrementor constInc(numElems);
    srand(1);
    for (int i = 0; i < numInc; ++i)
    {
        const int index = rand() % numElems;
        linearInc.incrementAt(index);
        constInc.incrementAt(index);
        for (int j = 0; j < numElems; ++j)
        {
            if (linearInc.valueAt(j) != constInc.valueAt(j))
            {
                printf("Error: differing values at increment step %d, value at index %d\n", i, j);
            }
        }
    }
    return 0;
}

Answer 7

只需从修改后的元素沿数组迭代，直到找到正确的位置，然后交换。平均案例复杂度为 O(N)，其中 N 是平均重复次数。最坏的情况是 O(n)，其中 n 是数组的长度。只要 N 不大并且不会随着 n 严重扩展，你就可以，并且出于实际目的可能会假装它是 O(1)。

如果重复是常态和/或与 n 强烈缩放，那么有更好的解决方案，请参阅其他响应。

Answer 8

是和不是。

是的，如果列表仅包含唯一整数，因为这意味着您只需要检查下一个值。没有在任何其他情况下。如果这些值不是唯一的，则递增 N 个重复值中的第一个意味着它必须移动 N 个位置。如果值是浮点数，则 x 和 x+1 之间可能有数千个值

Answer 9

非常清楚要求很重要；最简单的方法是将问题表达为 ADT（抽象数据类型），列出所需的操作和复杂性。

这就是我认为您正在寻找的内容：提供以下操作的数据类型：

• Construct(n): 创建一个大小n为的新对象0。

• Value(i): 返回 index 处的值i。

• Increment(i): 增加 index 处的值i。

• Least()：返回具有最小值的元素的索引（如果有多个，则返回一个这样的元素）。

• Next(i)i：返回从 开始的排序遍历中元素之后的下一个元素的索引Least()，这样遍历将返回每个元素。

除了构造器，我们希望上述每一个操作都具有复杂性O(1)。我们还希望对象占据O(n)空间。

该实现使用存储桶列表；每个桶都有一个value和一个元素列表。每个元素都有一个索引，一个指向它所在的桶的指针。最后，我们有一个指向元素的指针数组。（在 C++ 中，我可能会使用迭代器而不是指针；在另一种语言中，我可能会使用侵入式列表。）不变量是没有桶永远是空的，并且value桶的 是严格单调递增的。

我们从一个值为 0 的存储桶开始，其中包含一个n元素列表。

Value(i)通过返回i数组元素处的迭代器引用的元素的桶的值来实现。Least()是第一个桶中第一个元素的索引。Next(i)是迭代器在 element 处引用的元素之后的下一个元素的索引i，除非该迭代器已经指向列表的末尾，在这种情况下，它是下一个桶中的第一个元素，除非该元素的桶是最后一个桶，在这种情况下，我们位于元素列表的末尾。

唯一感兴趣的接口是Increment(i)，如下所示：

• 如果 elementi是其桶中唯一的元素（即桶列表中没有下一个元素，并且 elementi是桶列表中的第一个元素）：

  • 增加关联存储桶的值。
  • 如果下一个bucket的值相同，则将下一个bucket的元素列表追加到这个bucket的元素列表中（这是O(1)，不管list的大小，因为它只是一个指针交换），然后删除下一个bucket。

• 如果 elementi不是其存储桶中的唯一元素，则：

  • 将其从存储桶列表中删除。
  • 如果下一个桶具有下一个顺序值，则将元素推i送到下一个桶的列表中。
  • 否则，下一个bucket的值更大，然后创建一个具有下一个顺序值和唯一元素的新bucket，i并将其插入到这个bucket和下一个bucket之间。

Answer 10

作为对其他答案的补充：如果您只能拥有数组，那么您确实不能保证操作将是恒定时间的；但是因为数组是排序的，你可以在操作中找到相同数字的运行结束log n，而不是在n操作中。这只是一个二进制搜索。

如果我们希望大多数数字运行都很短，我们应该使用疾驰搜索，这是一种变体，我们首先通过查看位置 +1、+2、+4、+8、+16 等来找到边界，然后在里面做二分查找。您会得到一个通常不变的时间（如果项目是唯一的，则非常快），但可以增长到log n. 除非出于某种原因，即使在多次更新之后，长时间运行的相同数字仍然很常见，否则这可能优于任何需要保留额外数据的解决方案。