LeetCode Problem 35: Search Insert Position in JavaScript

28.03.2024

Zusammenfassung

Eine prägnante Lösung für LeetCodes Search Insert Position Problem, die mit linearer Suche findet, wo ein Zielwert in einem sortierten Array hingehört, und dabei exzellente Laufzeit-Performance erreicht.

Einleitung

Hallo zusammen, heute habe ich mich an LeetCode Problem 35: Search Insert Position gewagt. Es ist ein großartiges Übungsproblem für Anfänger wie mich, auch wenn es auf der leichteren Seite ist. Wie üblich werde ich es in JavaScript lösen. Lasst uns eintauchen!

Das Problem erklärt

Dieses Problem verlangt von euch, den korrekten Einfügepunkt für eine gegebene Ganzzahl (target
) innerhalb eines sortierten Arrays (nums
) zu finden. Das resultierende Array sollte seine sortierte Ordnung beibehalten.

Beispiel:

Betrachtet das Array nums = [1, 3, 5, 6]
 und das Ziel target = 5
. Die Funktion sollte 2
 zurückgeben, weil das Einfügen von 5
 an Index 2 das Array sortiert hält: [1, 3, 5, 6]
.

Wichtige Punkte:

Das Array
```
nums
```
ist immer in aufsteigender Reihenfolge sortiert.
Das Ziel
```
target
```
könnte bereits im Array existieren oder auch nicht.
Wenn das Ziel größer ist als alle Elemente in
```
nums
```
, sollte es am Ende eingefügt werden (Index
```
nums.length
```
).

Die Lösung

Erste Idee

Bei meinem ersten Ansatz für dieses Problem überlegte ich, durch das nums-Array zu iterieren. Wenn wir auf einen Wert in nums[i] stoßen, der größer oder gleich dem Ziel ist, können wir die Schleife unterbrechen und diesen Index als Einfügepunkt zurückgeben.

var searchInsert = function(nums, target) {
    for(let i=0; i<nums.length; i++){
        if(nums[i] >= target){
            return i
            break
        }
    }
}

Bei meinem ersten Ansatz für dieses Problem überlegte ich, durch das nums-Array zu iterieren. Wenn wir auf einen Wert in nums[i] stoßen, der größer oder gleich dem Ziel ist, können wir die Schleife unterbrechen und diesen Index als Einfügepunkt zurückgeben.

return nums.length

Der finale Code

Um zu testen, ob es funktioniert, reichen wir diesen finalen Code ein:

var searchInsert = function(nums, target) {
    for(let i=0; i<nums.length; i++){
        if(nums[i] >= target){
            return i
            break
        }
    }
    return nums.length
};

Um seine Funktionalität zu überprüfen, haben wir den finalen Code eingereicht. Das Feedback zeigte Erfolg! Der Code hat eine beeindruckende Laufzeit von 44ms und übertrifft damit 92,07% der anderen JavaScript-Einreichungen. Zusätzlich nutzt er nur 49,2MB Speicher und übertrifft damit 22,54% der Konkurrenz.

Falls ihr eine bessere Lösung gefunden habt, kontaktiert mich gerne und zeigt sie mir.

Abschließende Worte

Ich hoffe, es hat euch Spaß gemacht, diesen Artikel zu lesen.

Falls ihr Fragen oder Anmerkungen habt, kontaktiert mich gerne.

Euer Mario 💚