[LeetCode]238. Ideen zur Lösung des Produkts anderer Arrays als sich selbst

Titel

Geben Sie ein ganzzahliges Array nums der Länge n, wobei n > 1, und geben Sie die Ausgabe des Ausgabearrays zurück, wobei Output[i] allen anderen Elementen in nums außer nums[i] Produkt entspricht von .

Beispiel:

Eingabe: [1,2,3,4]
Ausgabe: [24,12,8,6]

Tipps: Die Fragedaten stellen sicher, dass das Produkt aller Präfixelemente und Suffixe (sogar des gesamten Arrays) jedes Elements im Array im Bereich von 32-Bit-Ganzzahlen liegt.

Anleitung: Bitte verwenden Sie keine Division und lösen Sie diese Frage innerhalb von O(n) Zeitkomplexität.

Erweitert: Können Sie dieses Problem innerhalb einer konstanten Raumkomplexität lösen? (Zum Zweck der Raumkomplexitätsanalyse wird das Ausgabearray nicht als zusätzlicher Raum betrachtet.)

Lösung

Der erste Gedanke, nachdem ich die Frage gestellt habe, ist: zwei für Schleifen, eine für das Produkt und eine für die Division. Aber später stellte ich fest, dass in den Anweisungen stand, keine Division zu verwenden, also musste ich andere Methoden verwenden.

Da wir außer uns selbst die kumulative Multiplikation berechnen, können wir die aktuelle Position als Teilungspunkt verwenden, um das Produkt der Elemente auf der linken Seite bzw. das Produkt der Elemente auf der rechten Seite zu berechnen, und dann multipliziere sie.

Dies hat die folgende Lösung:

Algorithmus 1 (aus der offiziellen LeetCode-Lösung extrahiert):

Initialisieren Sie zwei leere Arrays L und R. Für einen gegebenen Index i repräsentiert L[i] das Produkt aller Zahlen links von i und R[i] repräsentiert das Produkt aller Zahlen rechts von i.

Wir müssen zwei Schleifen verwenden, um die Werte der L- und R-Arrays zu füllen. Für das Array L sollte L[0] 1 sein, da sich links vom ersten Element kein Element befindet. Für andere Elemente: L[i] = L[i-1] * nums[i-1].

Ähnlich sollte für das Array R R[length-1] 1 sein. Länge bezieht sich auf die Größe des Eingabearrays. Andere Elemente: R[i] = R[i+1] * nums[i+1].

Wenn die R- und L-Arrays gefüllt sind, müssen wir nur über das Eingabearray iterieren, und der Wert am Index i ist: L[i] * R[i].

class Solution {
    public int[] productExceptSelf(int[] nums) {
  int arrLen = nums.length;
  int[] leftNums = new int[arrLen];
  int[] rightNums = new int[arrLen];
  leftNums[0] = 1;rightNums[arrLen-1] = 1;
  
  for(int i = 1; i < arrLen; i++){
   leftNums[i] = leftNums[i-1] * nums[i-1];
   rightNums[arrLen-i-1] = rightNums[arrLen-i] * nums[arrLen-i];
  }
  
  for(int i = 0; i < arrLen; i++){
   leftNums[i] *= rightNums[i];
  }
  
  return leftNums;
 }
}

Komplexitätsanalyse

Zeitkomplexität: O(N), wobei N sich bezieht auf die Größe der Array-Nummern. Die Vorverarbeitung der L- und R-Arrays und die endgültige Durchlaufberechnung sind beide O(N)-zeitkomplex.

Raumkomplexität: O(N), wobei N sich auf die Größe der Array-Nummern bezieht. Die L- und R-Arrays werden zum Erstellen der Antwort verwendet. Die Länge der L- und R-Arrays entspricht der Größe der Array-Nummern.

Algorithmus 2: Shared-Array-Methode

Die Gesamtidee ist dieselbe wie die offizielle Problemlösungsidee: Linke Multiplikation * rechte Multiplikation.

Definieren Sie das Rückgabearray returnNums und betrachten Sie es als gemeinsam genutztes Array, während Sie Daten vom linken und rechten Ende füllen und dann links und rechts definieren, um das linke zu speichern und richtige Produkte und Schleifeniteration erneuern.

1. Bevor sich die beiden Zeiger treffen, füllen Sie einfach das Array.

2. Wenn die beiden interagieren (passiert nur bei ungerader Länge), wird der Füllwert angezeigt ist links*rechts.

3. Nachdem sich die beiden getroffen haben, sollte der Wert des Arrays mit dem Endwert ausgefüllt werden: Da der linke Teil bereits das linke Produkt gespeichert hat und das rechte Produkt bald verfügbar sein wird berechnet; der rechte Teil hat das richtige Produkt gespeichert, wir sind dabei, das linke Produkt zu erhalten. Also einfach direkt multiplizieren. returnNums[i] = left und returnNums[j] = right.

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int arrLen = nums.length;
        int[] returnNums = new int[arrLen];
        int left = 1, right = 1;    // 临时存储
        returnNums[0] = 1; returnNums[arrLen-1] = 1;
        for(int i = 1, j = arrLen-2; i < arrLen; i++, j--){
            left *= nums[i-1];
            right *= nums[j+1];
            if(i < j){  // 两指针为交会
                returnNums[i] = left;
                returnNums[j] = right;
            }else if(i == j){   // 两指针重合，奇数位情况下发生
                returnNums[i] = left*right;
            }else{              // 两指针错位
                returnNums[i] *= left;
                returnNums[j] *= right;
            }
        }
        return returnNums;
    }
}

Komplexitätsanalyse

Zeitkomplexität: O(N ) Auf die gleiche Weise wie beim vorherigen Problem wird eine Schleife der Länge N ausgeführt, und ihre zeitliche Komplexität beträgt O(N).

Speicherplatzkomplexität: O(1), wie im Titel erwähnt, wird der Speicherplatz des zurückgegebenen Arrays nicht gezählt, sodass der zusätzlich genutzte Speicherplatz übrig bleibt und richtig. Daher gibt es nur eine Raumkomplexität mit konstantem Niveau.

Das obige ist der detaillierte Inhalt von[LeetCode]238. Ideen zur Lösung des Produkts anderer Arrays als sich selbst. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!