Set Array min vorwärts und rückwärts über Rekursion

Question

Sagen wir, ich habe ein Array A = {a1, a2, ..., an}

Angenommen, ein in Blöcke der Größe unterteilt ist b

Was ich versuche zu tun:

Lassen MinUntilHere und MinStartingHere sein 2-Arrays der Größe n, wobei gilt:

• MinUntilHere [i] = Minimum von Anfang Blocks i bis i
• MinStartingHere [i] = Minimum von i bis zum Ende des i-Block

ich diese 2 Felder ausfüllen möchten in einem einzigen Quer im Array ... ich habe versucht, den folgenden Pseudo-Code:

int fill(int pos = 0){ 

    if(pos >= n) return INF 

    if(pos is the start index of a block){ //i % b == 0 
     MinUntilHere[pos] = A[pos] 
     MinStartingHere[pos] = min(A[pos], fill(i + 1)) 
    } 
    else{ 
     MinUntilHere[pos] = min(A[pos], A[pos - 1]) 
     MinStartingHere[pos] = min(A[pos], fill(i + 1)) 
     return MinStartingHere[pos] 
    } 
} 

aber wie Sie sehen können, ist es nicht vollständig, da sie nicht erkennen können, wenn jeder Block vorbei ist und einige kehren fehlen . Wie kann ich eine Funktion erstellen, die nur einmal durch das Array geht und meine Antworten berechnet?

Example: 

Let A = {2,1,3,6,5,4}und b = 2 müssen die Arrays wie folgt gefüllt werden:

MinUntilHere = {2,1,3,3,5,4} 

MinStartingHere = {1,1,3,6,4,4} 

MinUntilHere [0 ] = 2 Ursache vom Anfang des 0-Blocks bis zum Index 0 ist das Minimum 2.

MinUntilHere [1] = 1 Ursache vom Anfang des Blocks 1 bis zum Index 1, das Minimum ist min (1,2) = 1

End of Example 

Answer 1

Im allgemeinen Fall können Sie nicht hoffen, die Arrays in einem einzigen Durchgang zu füllen.

Zum Beispiel, wenn die Blockgröße N (gesamte Array), dann den Eintrag füllen MinUntilHere[i], müssen Sie auf alle Artikel angesehen haben, bevor i und den Eintrag zu füllen MinStartingHere[i] Sie auf alle Artikel ausgesehen haben müssen nach i.

Answer 2

können Sie die folgenden verwendet werden, die den Job in 2 Passagen tut:

template <typename InputIt, typename OutputIt> 
void ComputeMinUntilHere(InputIt begin, InputIt end, OutputIt output) 
{ 
    if (begin == end) { 
     return; 
    } 
    auto min = *begin; 
    while (begin != end) { 
     min = std::min(min, *begin); 
     *output = min; 
     ++begin; 
     ++output; 
    } 
} 

struct MinByBlock 
{ 
    std::vector<int> minUntilHere; 
    std::vector<int> minStartingHere; 
}; 

MinByBlock ComputeMinByBlock(const std::vector<int>&v, std::size_t blockSize) 
{ 
    MinByBlock res; 
    res.minUntilHere.resize(v.size()); 
    res.minStartingHere.resize(v.size()); 
    for (std::size_t i = 0; i < v.size(); i += blockSize) { 
     const auto blockBegin = v.begin() + i; 
     const auto blockEndIndex = std::min(i + blockSize, v.size()); 
     const auto blockEnd = v.begin() + blockEndIndex; 

     ComputeMinUntilHere(blockBegin, blockEnd, res.minUntilHere.begin() + i); 
     ComputeMinUntilHere(std::make_reverse_iterator(blockEnd), 
          std::make_reverse_iterator(blockBegin), 
          std::make_reverse_iterator(res.minStartingHere.begin() + blockEndIndex)); 
    } 
    return res; 
} 

Demo

Sie können feststellen, als minUntilHere und minUntilHere ähnlich sind und kommt nur, wenn Sie von links nach rechts oder von rechts iterieren nach links.

ComputeMinUntilHere machen Sie den Job für eine ganze Reihe.

ComputeMinByBlock Den Vektor durch unabhängige Blöcke aufteilen, um das Ergebnis blockweise auszufüllen.

Answer 3

Sorry Leute, aber ich konnte eine lineare Lösung finden (das Array nur einmal ausführen) mit Code viel kleiner. Das ist die Lösung:

int fill(int pos = 0){ 

    if(pos >= |A|) return INF; 

    int mod = pos % b; 

    if(mod == 0){ 
     MinUntilHere[pos] = A[pos]; 
     MinStartingHere[pos] = min(A[pos], fill(pos + 1)); 
     return fill(pos + bsize); 
    } 
    else if(mod == bsize - 1){ 
     MinUntilHere[pos] = min(MinUntilHere[pos-1], A[pos]); 
     return MinStartingHere[pos] = A[pos]; 
    } 
    else{ 
     MinUntilHere[pos] = min(MinUntilHere[pos-1], A[pos]); 
     return MinStartingHere[pos] = min(A[pos], fill(pos + 1)); 
    } 

} 

Es funktioniert wie folgt:

• Wenn ich beginne den Block, setzen MinUntilHere als A [pos] Element und machen den MinStartingHere [pos] als Minimum von A [pos] und die Rückkehr von Füllung (pos + a);
• Wenn es nicht Anfang oder Ende eines Blocks ist, dann mache MinUntilHere [pos] = min (A [pos], MinUntilHere [pos-1]) und setze ihn für MinStartingHere als Minimum zwischen A [pos] und fülle (pos + 1) und gib ihn zurück (zur vorherigen Rekursion)
• Wenn es ein Blockende ist, mach dasselbe für MinUntilHere, und für MinStartingHere, setze es einfach als A [pos] und gib es zu den vorherigen Rekursionen zurück.

Ein wichtiges Detail ist, dass, wenn Sie den Block starten, können Sie eine Menge Rekursion anrufen und dann mit dem Wert für MinStartingHere zu Beginn dieses Blocks zurückkommen, und nach, dass Sie die Methode für die pos rufen + b Das bedeutet, dass nach der Beendigung des aktuellen Blocks ein neuer Block berechnet wird. sowieso

Danke für die Hilfe :)