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:

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;
    }
}

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;
    }
}

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;
    }
}

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!