Typescript Coding Chronicles: Produkt von Array außer sich selbst

Problemstellung:

Geben Sie bei einem gegebenen ganzzahligen Array nums eine Array-Antwort zurück, sodass Antwort[i] gleich dem Produkt aller Elemente von nums außer nums[i] ist.

Das Produkt eines beliebigen Präfixes oder Suffixes von Zahlen passt garantiert in eine 32-Bit-Ganzzahl.

Sie müssen einen Algorithmus schreiben, der in O(n)-Zeit und ohne Verwendung der Divisionsoperation ausgeführt wird.

Beispiel 1:

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

Beispiel 2:

• Eingabe: nums = [-1,1,0,-3,3]
• Ausgabe: [0,0,9,0,0]

Einschränkungen:

• 2 <= nums.length <= 10^5
• -30 <= nums[i] <= 30
• Das Produkt eines beliebigen Präfixes oder Suffixes von Zahlen passt garantiert in eine 32-Bit-Ganzzahl.

Nachverfolgen:

Können Sie das Problem in O(1) mit zusätzlicher Raumkomplexität lösen? (Das Ausgabearray zählt nicht als zusätzlicher Speicherplatz für die Raumkomplexitätsanalyse.)

Erster Denkprozess:

Um dieses Problem zu lösen, müssen wir das Produkt aller Elemente außer dem aktuellen Element berechnen, ohne die Divisionsoperation zu verwenden. Dies kann durch zwei Durchgänge über das Array erfolgen:

1. Berechnen Sie die Präfixprodukte für jedes Element.
2. Berechnen Sie die Suffixprodukte für jedes Element und multiplizieren Sie sie mit den Präfixprodukten.

Grundlegende Lösung:

Wir können zwei Arrays verwenden, um die Präfix- und Suffixprodukte zu speichern und sie dann zu multiplizieren, um das Endergebnis zu erhalten.

Code:

function productExceptSelf(nums: number[]): number[] {
    const n = nums.length;
    const prefixProducts = new Array(n).fill(1);
    const suffixProducts = new Array(n).fill(1);
    const result = new Array(n).fill(1);

    // Compute prefix products
    for (let i = 1; i < n; i++) {
        prefixProducts[i] = prefixProducts[i - 1] * nums[i - 1];
    }

    // Compute suffix products
    for (let i = n - 2; i >= 0; i--) {
        suffixProducts[i] = suffixProducts[i + 1] * nums[i + 1];
    }

    // Compute the result by multiplying prefix and suffix products
    for (let i = 0; i < n; i++) {
        result[i] = prefixProducts[i] * suffixProducts[i];
    }

    return result;
}

Zeitkomplexitätsanalyse:

• Zeitkomplexität: O(n), wobei n die Länge des Arrays ist. Wir durchlaufen das Array dreimal.
• Raumkomplexität: O(n), zum Speichern der Präfix- und Suffixprodukte.

Einschränkungen:

Die Basislösung funktioniert gut, benötigt aber zusätzlichen Platz zum Speichern von Präfix- und Suffixprodukten.

Optimierte Lösung:

Wir können die Lösung optimieren, um O(1) zusätzlichen Speicherplatz zu nutzen, indem wir das Ausgabearray zunächst zum Speichern von Präfixprodukten verwenden und es dann direkt ändern, um die Suffixprodukte einzuschließen.

Code:

function productExceptSelfOptimized(nums: number[]): number[] {
    const n = nums.length;
    const result = new Array(n).fill(1);

    // Compute prefix products in the result array
    for (let i = 1; i < n; i++) {
        result[i] = result[i - 1] * nums[i - 1];
    }

    // Compute suffix products and multiply with the prefix products
    let suffixProduct = 1;
    for (let i = n - 1; i >= 0; i--) {
        result[i] = result[i] * suffixProduct;
        suffixProduct *= nums[i];
    }

    return result;
}




<h3>
  
  
  Zeitkomplexitätsanalyse:
</h3>

<ul>
<li>
<strong>Zeitkomplexität:</strong> O(n), wobei n die Länge des Arrays ist. Wir durchlaufen das Array zweimal.</li>
<li>
<strong>Raumkomplexität:</strong> O(1), da wir das Ausgabearray zum Speichern von Zwischenergebnissen verwenden und keinen zusätzlichen Platz verbrauchen.</li>
</ul>

<h3>
  
  
  Verbesserungen gegenüber der Basislösung:
</h3>

<ul>
<li>Die optimierte Lösung reduziert die Raumkomplexität auf O(1), indem das Ausgabearray für Zwischenergebnisse verwendet wird.</li>
</ul>

<h2>
  
  
  Randfälle und Tests:
</h2>

<h3>
  
  
  Randfälle:
</h3>

<ol>
<li>Das Array enthält Null(en).</li>
<li>Das Array enthält negative Zahlen.</li>
<li>Die Array-Länge ist die minimale (2) oder maximale (10^5) Grenze.</li>
</ol>

<h3>
  
  
  Testfälle:
</h3>



<pre class="brush:php;toolbar:false">console.log(productExceptSelf([1,2,3,4])); // [24,12,8,6]
console.log(productExceptSelf([-1,1,0,-3,3])); // [0,0,9,0,0]
console.log(productExceptSelf([2,2,2,2])); // [8,8,8,8]
console.log(productExceptSelf([0,0])); // [0,0]
console.log(productExceptSelf([5])); // This should not be a valid input as the minimum length is 2
console.log(productExceptSelf([1,2])); // [2, 1]

console.log(productExceptSelfOptimized([1,2,3,4])); // [24,12,8,6]
console.log(productExceptSelfOptimized([-1,1,0,-3,3])); // [0,0,9,0,0]
console.log(productExceptSelfOptimized([2,2,2,2])); // [8,8,8,8]
console.log(productExceptSelfOptimized([0,0])); // [0,0]
console.log(productExceptSelfOptimized([5])); // This should not be a valid input as the minimum length is 2
console.log(productExceptSelfOptimized([1,2])); // [2, 1]

Allgemeine Problemlösungsstrategien:

1. Verstehen Sie das Problem:Lesen Sie die Problemstellung sorgfältig durch, um die Anforderungen und Einschränkungen zu verstehen.
2. Schlüsseloperationen identifizieren: Bestimmen Sie die erforderlichen Schlüsseloperationen, z. B. die Berechnung von Präfix- und Suffixprodukten.
3. Für Lesbarkeit optimieren:Verwenden Sie eine klare und prägnante Logik, um sicherzustellen, dass der Code leicht zu befolgen ist.
4. Gründlich testen:Testen Sie die Lösung mit verschiedenen Fällen, einschließlich Randfällen, um die Richtigkeit sicherzustellen.

Identifizieren ähnlicher Probleme:

1. Präfix-Summen-Array:

   • Probleme, bei denen Sie Präfixsummen für Bereichsabfragen berechnen müssen.
   • Beispiel: Bereichssummenabfrage.

2. In-Place-Algorithmen:

   • Probleme, bei denen Vorgänge vor Ort mit begrenztem zusätzlichem Platz durchgeführt werden müssen.
   • Beispiel: Drehen Sie ein Array um k Schritte nach rechts.

3. Array-Manipulation:

   • Probleme, bei denen Sie Arrays basierend auf bestimmten Bedingungen ändern müssen.
   • Beispiel: Nullen an das Ende eines Arrays verschieben.

Abschluss:

• Das Problem der Berechnung des Produkts eines Arrays außer self kann effizient gelöst werden, indem sowohl ein grundlegender Ansatz mit zusätzlichem Platz als auch ein optimierter In-Place-Ansatz verwendet werden.
• Es ist entscheidend, das Problem zu verstehen und es in überschaubare Teile zu zerlegen.
• Die Verwendung klarer Logik und die Optimierung der Lesbarkeit stellen sicher, dass die Lösung leicht zu befolgen ist.
• Tests mit verschiedenen Randfällen stellen die Robustheit sicher.
• Das Erkennen von Mustern in Problemen kann dabei helfen, ähnliche Lösungen auf andere Herausforderungen anzuwenden.

Durch das Üben solcher Probleme und Strategien können Sie Ihre Problemlösungsfähigkeiten verbessern und besser auf verschiedene Programmierherausforderungen vorbereitet sein.

Das obige ist der detaillierte Inhalt vonTypescript Coding Chronicles: Produkt von Array außer sich selbst. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!