Das Suchen eines Arrays nach Ganzzahlen in einem bestimmten Bereich

Question

Kann jemand Ideen für das folgende Problem geben?

Gegeben sei ein Array ar[] der Länge n und einige Abfragen. Jede Abfrage hat die Form a, b, c, finde die Zahl mit dem kleinsten Index i, so dass der Index im Bereich [c, n] liegt und so dass a < ar[i] < b. Insgesamt gibt es (n - 1), c geht von 1 bis n - 1. Die erwartete Komplexität für jede Abfrage sollte ungefähr O(log n) betragen, und eine Vorverarbeitung mit einer maximalen Komplexität von höchstens O(n log n) ist angemessen. Intuitiv kam mir ein Segmentbaum in den Sinn, aber ich konnte mir keine Möglichkeit vorstellen, ihn zu erstellen, noch was in jedem Knoten gespeichert werden sollte.

Answer 1

Ok, ich dachte, ich sollte die Lösung O(nlogn)/O(logn) implementieren, über die ich mit Benutzer12861 gesprochen habe.

Der Code funktioniert durch den Aufbau von n Bäumen, einem für jedes c. Jeder Baum teilt den größten Teil seines Inhalts mit den kleineren, mit maximal logn neuen Knoten. Auf diese Weise ist der Gesamtspeicher- und Zeitbedarf für die Vorverarbeitung auf O(nlogn) begrenzt.

Die tatsächlichen Bäume ähneln recht stark Intervallbäumen. Die Knoten speichern den minimalen und maximalen Wert, den sie abdecken, und den kleinsten Index, den sie enthalten. Meine Implementierung ist jedoch nicht selbstausgleichend, aber das kann mit Ihren bevorzugten Heuristiken hinzugefügt werden.

import sys

class Node:
    pass
class Interval(Node):
    def __init__(self,left,val,i,right):
        self.i = i; self.val = val
        self.left = left; self.right = right
        self.mini = min(left.mini, i, right.mini)
        self.min = min(left.min, val, right.min)
        self.max = max(left.max, val, right.max)
    def add(self,val,i):
        # Hier führen wir naive Einfügungen durch. In einer echten O(logn)-Lösung würden hier selbstausgleichende Maßnahmen ergriffen.
        if (val,i) < (self.val,self.i): return Interval(self.left.add(val,i), self.val, self.i, self.right)
        if (self.val,self.i) < (val,i): return Interval(self.left, self.val, self.i, self.right.add(val,i))
        return self
    def query(self,a,b):
        # Wenn das gesamte Intervall abgedeckt ist, geben Sie mini zurück. Dies hält uns maximal bei 2 geöffneten Knoten pro Ebene im Baum.
        if a <= self.min and self.max <= b: return self.mini
        # Andernfalls erstellen Sie eine Antwort aus den Unterbäumen.
        res = sys.maxint
        if a <= self.val <= b: res = min(res, self.i)
        if self.left.min <= b and self.left.max >= a: res = min(res, self.left.query(a,b))
        if self.right.min <= b and self.right.max >= a: res = min(res, self.right.query(a,b))
        return res
class Tip(Node):
    def __init__(self):
        # Dies ist ein typisches Beispiel für ein Nullmuster-Idiom. Die self.values sind auf die Min-/Max-Identitäten eingestellt, um sicherzustellen, dass keine Beeinträchtigung der aufwärts gerichteten Werteverbreitung stattfindet.
        self.mini = sys.maxint
        self.min = sys.maxint
        self.max = -sys.maxint
    def add(self,val,i):
        return Interval(Tip(), val, i, Tip())
    def query(self,a,b):
        return sys.maxint

# Das Eingabearray
data = [0, 3, 1, 2, 0, 4, 9, 6, 1, 7]
N = len(data)

# Array der Bäume aufbauen. O(nlogn)
ar = [None]*N + [Tip()]
for i in range(N-1, -1, -1):
    ar[i] = ar[i+1].add(data[i],i)

# Die Abfragefunktion. O(logn)
def query(a,b,c):
    return ar[c].query(a,b)

# Test
print query(2, 7, 4) # = 5

Answer 2

Bist du durch dies gegangen? Ich denke, es wird dir helfen, die Struktur zu verstehen und eine Möglichkeit zu überlegen, sie zu erstellen. Der Rest kann eine Menge Vergleiche sein.

Answer 3

Ich habe die Technik von Mason Bryant modifiziert, um etwas zu finden, das funktioniert. Die Probleme waren mehr Fehler in FindLowestIndex und ein größerer Fehler bei der Suche im Baum (es können mehrere Ergebnisse zurückgegeben werden).

Aber auch nach dieser Arbeit löst es das eigentliche Problem nicht. Die Zeit O(n log n) zum Einrichten ist einfach genug, aber wenn ich diese Technik verwende, kann ich nur eine Abfragezeit O((log n)^2) erhalten. Ich frage mich, ob Sie einen Link zum ursprünglichen Problem haben, falls dort weitere Erläuterungen vorhanden sind? Oder frage ich mich, ob das Problem wirklich lösbar ist. Oder vielleicht ist O((log n)^2) "ungefähr" O(log n), wie vom Problem verlangt, es ist sowieso weniger als O(n).

Die Technik besteht darin, unser Array in einem typischen Segmentsbaum zu speichern, aber zusammen mit den üblichen Segmentinformationen speichern wir auch alle Indizes der Elemente unter jedem Knoten in der Reihenfolge. Dieser zusätzliche Speicher dauert nur eine zusätzliche Zeit O(n log n), wenn Sie es ordentlich hinzufügen (n Elemente auf jedem der log n Ebenen gespeichert), daher beeinträchtigt dies unsere Einrichtungszeit nicht auf eine Weise, die zählt. Dann fragen wir den Baum ab, um die minimal notwendige Knotenmenge zu finden, die von unserem Bereich (a, b) enthalten ist. Diese Abfrage dauert ungefähr die gleiche Zeit wie eine typische Segmentbaumabfrage (O(log n)) und findet höchstens etwa 2*log n übereinstimmende Segmente. Während wir abfragen, finden wir den niedrigsten Index in jedem übereinstimmenden Segment, der unserer Bedingung c entspricht. Wir können einen Binärsuchvorgang verwenden, um diesen Index zu finden, da wir die Indizes in der Reihenfolge behalten haben, daher dauert dies im schlimmsten Fall O(log n) für jeden übereinstimmenden Knoten. Wenn wir alles angemessen zusammenzählen, beträgt die Gesamtzeit O((log n)^2).

Lassen Sie mich wissen, welche Schritte Sie gerne erklärt hätten.

C#-Code:

void Test() {
  DateTime start;
  TimeSpan at = new TimeSpan(), bt = new TimeSpan();

  Random rg = new Random();
  for(int i = 0; i < 20; i++) {
    // Arrays von 5 bis 10000 Elementen lang erstellen, Zufallswerte zwischen 0 und 100
    // Der Break-even-Zeitpunkt für Abfragen liegt bei etwa 10000 Elementen im Array für die verwendeten Werte und Abfragen
    int[] array = (from n in Enumerable.Range(1, rg.Next(5, 10000)) select rg.Next(0, 100)).ToArray();

    // Einrichtung sollte O(n log n) Zeit/Platz benötigen
    ArraySearcher Searcher = new ArraySearcher(array);

    // Jedes Array eine Anzahl von Malen gleich seiner Länge testen, mit Zufallswerten für a, b, c
    for(int j = 0; j < array.Length; j++) {
      int a = rg.Next(-1, 101), b = rg.Next(a, 102), c = rg.Next(0, array.Length);
      start = DateTime.Now;
      int expected = BruteSearch(array, a, b, c);
      at += DateTime.Now - start;
      // Die Suche sollte O(log n) Zeit dauern, ist aber in Wirklichkeit O((log n)^2) :(
      start = DateTime.Now;
      int got = Searcher.QuickSearch(a, b, c);
      bt += DateTime.Now - start;
      System.Diagnostics.Debug.Assert(got == expected);
    }
  }
  MessageBox.Show(at.ToString() + ", " + bt.ToString());
}

int BruteSearch(int[] array, int a, int b, int c) {
  for(int i = c; i < array.Length; i++)
    if(a < array[i] && array[i] < b)
      return i;
  return -1;
}

class ArraySearcher {

  SegmentNode Root;
  List Nodes;

  public ArraySearcher(int[] array) {
    Nodes = array.Select((value, index) => new SegmentNode(value, value, new List { index }, null, null)).ToList();
    // Das Sortieren wird uns O(n log n) kosten
    Nodes.Sort();
    // Das Erstellen eines normalen Segmentsbaums dauert O(n log n)
    // Darüber hinaus speichert in diesem Baum jeder Knoten alle Indizes unterhalb in der richtigen Reihenfolge
    // Insgesamt gibt es n dieser Indizes auf jeder Baumebene, die in der Reihenfolge gehalten werden, ohne zusätzliche Zeitkosten
    // Es gibt log n Ebenen im Baum
    // Also werden beim Erstellen unserer Listen zusätzlich O(n log n) Zeit und Platz verwendet, was im Vergleich zum einfachen Sortieren die Big O-Notation nicht beeinträchtigt
    this.Root = SegmentNode.Merge(Nodes, 0, Nodes.Count - 1);
  }

  public int QuickSearch(int a, int b, int c) {
    return this.Root.FindLowestIndex(a, b, c);
  }

  class SegmentNode : IComparable {

    public int Min, Max;
    public List Indices;
    public SegmentNode Left, Right;

    public SegmentNode(int Min, int Max, List Indices, SegmentNode Left, SegmentNode Right) {
      this.Min = Min;
      this.Max = Max;
      this.Indices = Indices;
      this.Left = Left;
      this.Right = Right;
    }

    int IComparable.CompareTo(object other) {
      return this.Min - ((SegmentNode)other).Min;
    }

    public static SegmentNode Merge(List Nodes, int Start, int End) {
      int Count = End - Start;
      if(Start == End)
        return Nodes[Start];
      if(End - Start == 1)
        return SegmentNode.Merge(Nodes[Start], Nodes[End]);
      return SegmentNode.Merge(SegmentNode.Merge(Nodes, Start, Start + Count/2), SegmentNode.Merge(Nodes, Start + Count/2 + 1, End));
    }

    public static SegmentNode Merge(SegmentNode Left, SegmentNode Right) {
      int LeftCounter = 0, RightCounter = 0;
      List NewIndices = new List();
      while(LeftCounter < Left.Indices.Count || RightCounter < Right.Indices.Count) {
        if(LeftCounter < Left.Indices.Count && (RightCounter == Right.Indices.Count || Left.Indices[LeftCounter] < Right.Indices[RightCounter]))
          NewIndices.Add(Left.Indices[LeftCounter++]);
        else
          NewIndices.Add(Right.Indices[RightCounter++]);
      }
      return new SegmentNode(Left.Min, Right.Max, NewIndices, Left, Right);
    }

    public int FindLowestIndex(int SeekMin, int SeekMax, int c) {
      // Dies wird höchstens O(log n) übereinstimmende Segmente finden, immer weniger als 2 auf jeder Ebene des Baums
      // Jedes übereinstimmende Segment wird im schlimmsten Fall in O(log n) durchsucht
      // Insgesamt ergibt sich dies tatsächlich zu O((log n)^2), wenn Sie es richtig machen
      if(SeekMin < this.Min && SeekMax > this.Max)
        return FindLowestIndex(this.Indices, c);
      if(SeekMax <= this.Min || SeekMin >= this.Max)
        return -1;
      int LeftMatch = this.Left.FindLowestIndex(SeekMin, SeekMax, c);
      int RightMatch = this.Right.FindLowestIndex(SeekMin, SeekMax, c);
      if(LeftMatch == -1)
        return RightMatch;
      if(RightMatch == -1)
        return LeftMatch;
      return LeftMatch < RightMatch ? LeftMatch : RightMatch;
    }

    int FindLowestIndex(List Indices, int c) {
      int left = 0, right = Indices.Count - 1, mid = left + (right - left) / 2;
      while(left <= right) {
        if(Indices[mid] == c)
          return c;
        if(Indices[mid] > c)
          right = mid - 1;
        else
          left = mid + 1;
        mid = left + (right - left) / 2;
      }
      if(mid >= Indices.Count)
        return -1;
      // keine genaue Übereinstimmung, also den nächsthöheren Wert zurückgeben
      return Indices[mid];
    }
  }
}

Answer 4

Vielleicht fehlt mir etwas. Erfüllt das nicht Ihre Anforderungen?

for (int i = c; i < n; i++)
{
    if (a < ar[i] && ar[i] < b)
        return i;
}

Answer 5

Erstellen Sie ein Array von Indizes und sortieren Sie sie. Das heißt, gegeben das Array [20, 0, 10, 15, 5], würden Sie ein initiales Array erstellen [0, 1, 2, 3, 4]. Jetzt sortieren Sie das Array von Indizes, um die Elemente in sortierter Reihenfolge widerzuspiegeln. Die sortierten Indizes wären [1, 4, 2, 3, 0]. Sie enden mit zwei Arrays:

original = [20, 0, 10, 15, 5]
tag = [1, 4, 2, 3, 0]

Sie können das Original-Array durch das Tag-Array binär durchsuchen. Das heißt, Ihre Vergleichsfunktion vergleicht original[tag[x]] und original[tag[y]]. Das löst das "Wo ist der Index" Problem. Sie können dann die Binärsuche im Segment tag[c] ... tag[n] verwenden.

Scheint so, als ob das funktionieren sollte. Sie benötigen eine stabile Sortierung, damit gleiche Zahlen ihre relative Reihenfolge beibehalten.