Pflegen Sie einen sortierten array in O(1)?

Habe ich noch nicht gearbeitet, dies vollständig, aber ich denke, die Allgemeine Idee, die helfen könnte, für ganze zahlen zumindest. Auf Kosten von mehr Speicher, können Sie pflegen eine separate Daten-Struktur, die behauptet, das Ende der index einer Folge von wiederholten Werten (da der Sie Sie vertauschen möchten Ihre erhöhte Wert mit der Endung-index der wiederholte Wert). Dies ist, weil es mit wiederholten Werten, dass Sie in den schlimmsten Fall O(n) Laufzeit: angenommen, Sie haben [0, 0, 0, 0] und Sie erhöhen die Wertschöpfung am Standort 0. Dann ist es O(n) zu finden, aus der letzten Position (3).

Aber lassen Sie uns sagen, dass Sie pflegen die Daten-Struktur, die ich erwähnt (eine Karte funktioniert, weil es hat O(1) - lookup). In diesem Fall müssten Sie so etwas wie dieses:

0 -> 3

So haben Sie einen Lauf von 0 Werte, die enden an Ort 3. Wenn Sie erhöhen einen Wert, sagen wir am Standort i Sie überprüfen, um zu sehen, ob der neue Wert größer ist als der Wert, bei i + 1. Wenn es nicht, Sie sind in Ordnung. Aber wenn es ist, Sie schauen, um zu sehen, ob dort ein Eintrag für diesen Wert in der Sekundär-Daten-Struktur. Wenn nicht, können Sie einfach tauschen. Wenn es ist einen Eintrag, schaut Euch die Endung-index und dann tauschen mit dem Wert an dieser Position. Sie dann änderungen vornehmen, die Sie benötigen, um die sekundären Daten-Struktur entsprechend den neuen Zustand des Arrays.

Gründlicher Beispiel:

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

Die sekundären Daten-Struktur ist:

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

Sagen wir, Sie erhöhen die Wertschöpfung am Standort 2. So haben Sie erhöht 3 zu 4. Das array sieht jetzt wie folgt aus:

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

Schauen Sie auf das nächste element, das 3. Dann mal bis der Eintrag für das element in der Sekundär-Daten-Struktur. Der Eintrag ist 4, was bedeutet, dass es ein run-of - 3's, die Ende an 4. Dies bedeutet, dass Sie können, tauschen Sie den Wert von der aktuellen Position mit dem Wert bei index 4:

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

Nun müssen Sie auch zum aktualisieren der sekundären Daten-Struktur. Insbesondere, da der Lauf der 3's endet ein index früh, so dass Sie brauchen, um zu Dekrementieren diesen Wert:

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

Andere überprüfung, die Sie tun müssen, ist, um zu sehen, wenn der Wert wiederholt sich nicht mehr. Sie können es überprüfen, indem man die i - 1th und die i + 1th Orte, um zu sehen, wenn Sie die gleiche wie der Wert in Frage. Wenn weder gleich sind, dann Sie können entfernen Sie den Eintrag für diesen Wert von der Karte.

Wieder, dies ist nur eine Allgemeine Idee. Ich habe es code aus um zu sehen, ob es klappt wie ich dachte.

Bitte fühlen Sie sich frei, um poke Löcher.

UPDATE

Habe ich eine Implementierung dieses Algorithmus hier in JavaScript. Ich verwendet, JavaScript nur so konnte ich es schnell tun. Auch, weil ich codiert es sich ziemlich schnell, es kann vermutlich gereinigt werden. Ich habe die Kommentare allerdings. Ich bin mir nicht irgendetwas esoterisches, also das sollte einfach portierbar sein, um C++.

Gibt es im wesentlichen zwei Teile des Algorithmus: das Inkrementieren und austauschen (falls erforderlich), und der Buchführung erfolgt auf der Karte, die Spur hält unser Ende den Indizes läuft der wiederholten Werte.

Den code enthält eine Test-harness, beginnt mit einer Reihe von Nullen und Schritten zufälligen Positionen. Am Ende jeder iteration gibt es einen test, um sicherzustellen, dass das array sortiert ist.

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

Wenn die Werte klein sind, zählen, Sortieren, arbeiten wird. Stellen Sie das array [0,0,0,0] als {4}. Die Inkrementierung der null gibt {3,1} : 3 Nullen und eine eins. Im Allgemeinen erhöhen jeder x-Wert abziehen eines aus der Zählung von x und erhöht die Anzahl von {x+1}. Die flächeneffizienz ist O(N), obwohl, wo N ist der höchste Wert.

So nehmen Sie sortierte array und hashtable. Sie gehen über ein array, um herauszufinden, "flacher" Bereiche, in denen Elemente mit dem gleichen Wert. Für jedes flache Gebiet, die Sie haben, um herauszufinden, drei Dinge 1) wo es beginnt (index des ersten Elements) 2) was ist es Wert 3) was ist der Wert des nächsten Elements (die nächst größeren). Dann setzen Sie dieses Tupel in die Hash-Tabelle, wo die Schlüssel werden element Wert. Dies ist Voraussetzung, und es ist Komplexität eigentlich egal.

Dann, wenn Sie erhöhen einige element (index i) Sie look-up-Tabelle für den index der nächsten größeren element (nennen wir ihn j) und swap i mit i - 1. Dann 1) fügen Sie einen neuen Eintrag in der Hashtabelle vorhanden 2) update-Eintrag, für die es in den früheren Wert.

Mit perfekten Hashtabelle (oder begrenzten Bereich der möglichen Werte) es wird fast O(1). Der Nachteil: es wird nicht stabil sein.

Hier einige code:

#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;
}

Ist es wichtig, sehr klar über die Anforderungen, ist der einfachste Weg, um auszudrücken, das problem als ADT (Abstrakter Datentyp), Auflistung der erforderlichen Vorgänge und Komplexität.

Hier ist, was ich denke, du suchst: ein Datentyp bietet die folgenden Operationen:

• Construct(n): Erstellen Sie ein neues Objekt von der Größe n alle, deren Werte 0.

• Value(i): Gibt den Wert an index i.

• Increment(i): Erhöhen Sie den Wert bei index i.

• Least(): Return der index des Elements mit dem geringsten Wert (oder ein solches element, falls es mehrere gibt).

• Next(i): Return der index des nächsten Elements nach dem element i in eine sortierte Traversierung beginnend bei Least(), so dass die überquerung zurück jedes element.

Abgesehen von den Konstruktor, wir möchten, dass jeder der oben genannten Vorgänge zu haben, die Komplexität O(1). Wir wollen auch das Objekt zu besetzen O(n) Raum.

Die Implementierung verwendet eine Liste der Gruppen; jede Gruppe hat eine value und eine Liste von Elementen. Jedes element hat einen index, einen Zeiger, um den Eimer es gehört. Schließlich haben wir ein array von Zeigern auf Elemente. (In C++, ich würde wahrscheinlich verwenden Sie Iteratoren anstelle von Zeigern; in einer anderen Sprache, würde ich wahrscheinlich aufdringlich Listen.) Die Invarianten sind, dass keine Eimer ist immer leer, und die value der Eimer sind streng monoton Steigend.

Beginnen wir mit einem einzigen Eimer mit dem Wert 0, welches eine Liste von n Elemente.

Value(i) umgesetzt wird-auch durch Rücksendung der Wert der Eimer des Elements wird durch den iterator auf element i des Arrays. Least() ist der index des ersten Elements in der ersten Eimer. Next(i) ist der index des nächsten Elements nach der einen wird durch den iterator auf element i, es sei denn, dass der iterator wird jetzt schon darauf am Ende der Liste, in dem Fall ist es das erste element in der nächsten Eimer, es sei denn, das element der Eimer ist der Letzte Eimer, in dem Fall sind wir am Ende der element-Liste.

Die einzige Schnittstelle, die von Interesse ist Increment(i), die ist wie folgt:

• Wenn das element i ist das einzige element in Ihre Eimer ist (d.h. es gibt kein Nächstes element in der Liste Eimer, und element i ist das erste element in der Liste Eimer):

  • Erhöhen Sie den Wert des dazugehörigen Eimer.
  • Wenn der nächste Eimer hat den gleichen Wert, hängen Sie den nächsten Eimer ist element der Liste, um diese Eimer-element-Liste (diese ist O(1), unabhängig von der Liste die Größe, denn es ist nur ein Zeiger tauschen), und löschen Sie dann den nächsten Eimer.

• Wenn das element i ist nicht das einzige element in Ihre Eimer, dann:

  • Entfernen Sie es aus Ihrer Liste Eimer.
  • Wenn der nächste Eimer hat die nächste fortlaufende Wert, dann schieben Sie das element i auf den nächsten bucket-Liste.
  • Ansonsten, der nächste Eimer ist der Wert größer, dann erstellen Sie einen neuen bucket mit der nächsten sequenziellen Wert und nur element i aus und fügen Sie es zwischen dem Eimer und der nächste.

Ich denke, dass es möglich ist, ohne Verwendung einer hashtable. Ich habe eine Implementierung hier:

#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;
}