Beispielanalyse für Java-Array-Hochfrequenztestpunkte

1. Grundlagen der Array-Theorie

Ein Array ist eine Sammlung derselben Art von Daten, die im kontinuierlichen Speicherbereich gespeichert sind. Die entsprechenden Daten unter dem Index können durch Indexierung abgerufen werden.

Nehmen Sie eine Kastanie (Zeichenreihe)~

Sie können sehen:

1, Der Index des Arrays beginnt bei 0

2. Die Adresse des Arrays im Speicher ist fortlaufend

Beim Löschen von Elementen können Sie also nur das Überschreiben verwenden.

Wenn Sie beispielsweise das Element mit dem Index 2~ löschen möchten, müssen Sie die Elemente nach 2 der Reihe nach zum vorherigen verschieben und dabei das zu löschende Element abdecken. Durch das Löschen eines Elements wird also nicht der Platz des Elements freigegeben, sondern die folgenden Elemente werden nach vorne verschoben, wobei das zu löschende Element überschrieben wird und dann 1 von der Länge des Arrays abgezogen wird, um ein scheinbar neues Array zu erhalten.

In Java lautet die Speichermethode für zweidimensionale Arrays wie folgt:

2. Gemeinsame Testpunkte#🎜 🎜##🎜 🎜#1.Binäre Suche

Link zur Frage: Binäre Suche

Die Prämisse dieser Frage ist ein geordnetes Array, denn sobald es wiederholte Elemente gibt, Zur Rückgabe wird die binäre Suchmethode verwendet. Die Elementindizes dürfen nicht eindeutig sein. Dies sind Voraussetzungen für die Verwendung der Halbierungsmethode.

Die Idee der binären Suche ist:

Unter der Voraussetzung, dass das Array geordnet ist (aufsteigende Reihenfolge vorausgesetzt), wenn der Wert in der Mitte des Arrays größer ist Als der zu findende Wert liegt das zu findende Element möglicherweise nicht in der zweiten Hälfte, da die Werte in der zweiten Hälfte größer als der Mittelwert sind, sodass der Bereich durch den ersten Vergleich um die Hälfte reduziert werden kann Das Gleiche gilt später, das heißt, die Zeitkomplexität wird auf O (logN) reduziert und die Effizienz erheblich verbessert. Wenn die Zeitkomplexität zum Finden von Elementen in der Frage zuerst O (logN) sein muss ob es in zwei Teile geteilt werden kann?

class Solution {
    public int search(int[] nums, int target) {
        // 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1;
        }
        return -1;
    }
}

2. Elemente entfernen

Einige Schüler haben vielleicht gesagt, dass man die überflüssigen Elemente einfach löschen kann? Sie müssen jedoch wissen, dass die Elemente des Arrays in der Speicheradresse fortlaufend sind. Sie können ein Element im Array nicht einzeln löschen, sondern nur überschreiben.

Zum Beispiel: Ich gebe Ihnen ein Array und einen Val-Wert, und Sie möchten die Elemente im Array löschen, die dem Val-Wert entsprechen.

Idee 1: Brutale Methode

Wir können zwei for-Schleifen verwenden, die dem Val-Wert entsprechen, und das gesamte folgende Element wird nach vorne verschoben, um es abzudecken . Entfernen Sie die zu löschenden Elemente, aber dieser Ansatz ist offensichtlich zu zeitaufwändig.

class Solution {
    public int removeElement(int[] nums, int val) {
        int size = nums.length;
        for (int i = 0; i < size;i++ ) {
            if (nums[i] == val) { // 发现需要移除的元素，就将数组后面集体向前移动一位
                for (int j = i + 1; j < size; j++) {
                    nums[j - 1] = nums[j];
                }
                i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
                size--;
            }
        }
        return size;
    }
}

Idee 2: Doppelzeigermethode

Einrichten eines schnellen und langsamen Zeigers, langsamer schneller, beide bewegen sich zusammen und stoppen, wenn der langsame Zeiger auf das Element trifft gelöscht werden, und wartet darauf, gelöscht (überschrieben) zu werden. Wenn der schnelle Zeiger das zu verlassende Element erreicht, wird das Element des schnellen Zeigers dem langsamen Zeiger zugewiesen, und dann bewegen sich die beiden Zeiger gleichzeitig rückwärts, bis der schnelle Zeiger erreicht ist durchläuft das gesamte Array.

Es kann so verstanden werden: Definieren Sie die neue Länge des Arrays newLength, beginnend bei 0, definieren Sie einen schnellen Zeiger, um das Array schnell zu durchlaufen. Wenn Fast das zu verlassende Element erreicht, bedeutet dies, dass Das Element sollte dem neuen Array hinzugefügt werden (d. h. es wird dem newLength-Index hinzugefügt, was dem Teil des Arrays entspricht, bevor newLength als das neue Array zurückzugeben ist, was dem Einfügen von Elementen entspricht dieses neue Array).

class Solution {
    public int removeElement(int[] nums, int val) {
        int fast = 0;// 定义一个快指针遍历数组
        int newLength = 0;// 定义新的数组长度
        while(fast < nums.length){
            if(nums[fast] != val){
                nums[newLength++] = nums[fast];
            }
            fast++;
        }
        return newLength;
    }
}

Empfohlene Fragen zum erzwungenen Abzug

1. Duplikate im sortierten Array löschen

2. Nullen verschieben

3 . Vergleichen Sie Zeichenfolgen, die Backspaces enthalten , Ändern und Suchen Sobald Sie das Suchen und Löschen von Arrays beherrschen, können Sie mit der Lösung von Fragen beginnen.

Das obige ist der detaillierte Inhalt vonBeispielanalyse für Java-Array-Hochfrequenztestpunkte. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!