Exemple d'analyse de points de test haute fréquence de tableau Java

1. Bases de la théorie des tableaux

Un tableau est une collection du même type de données stockées dans un espace mémoire continu. Les données correspondantes sous l'indice peuvent être obtenues via l'indexation de l'indice.

Par exemple (tableau de caractères)~

Vous pouvez voir :

1. L'indice du tableau commence à 0

2 L'adresse du tableau dans la mémoire est continue

Donc lors de la suppression d'éléments. , ne peut être effectué que par écrasement.

Par exemple, si vous souhaitez supprimer l'élément d'index 2~, vous devez déplacer les éléments après 2 vers le précédent dans l'ordre, en couvrant l'élément à supprimer.

Ainsi, la suppression d'un élément ne libère pas l'espace de l'élément, mais déplace les éléments suivants vers l'avant, recouvrant l'élément à supprimer, puis en soustrayant 1 de la longueur du tableau , Vous obtiendrez un tableau apparemment nouveau.

En Java, la méthode de stockage des tableaux bidimensionnels est la suivante :

2 Points de test communs

1 Recherche binaire

Lien vers la question : Recherche binaire

La prémisse de cette question est. un tableau ordonné. Parce qu'une fois qu'il y a des éléments répétés, l'indice d'élément renvoyé par la méthode de recherche binaire peut ne pas être unique. Ce sont les conditions préalables à l'utilisation de la méthode de recherche binaire.

L'idée de la recherche binaire est la suivante :

En partant du principe que le tableau est ordonné (en supposant un ordre croissant), si la valeur au milieu du tableau est supérieure à la valeur à trouver, alors l'élément à trouver trouvé ne peut pas être dans la seconde moitié, car les valeurs dans la seconde moitié sont toutes supérieures à la valeur moyenne, donc grâce à la première comparaison, la plage peut être réduite de moitié. La même chose s'applique plus tard, c'est-à-dire que la complexité temporelle est réduite. à O(logN), et l'efficacité est grandement améliorée. Lorsque la question nécessite que la complexité temporelle de la recherche des éléments soit O(logN), demandez-vous d'abord si elle peut être divisée en deux ?

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. Supprimer des éléments

Certains étudiants ont peut-être dit : ne devriez-vous pas simplement supprimer les éléments redondants ? Mais il faut savoir que les éléments du tableau sont continus dans l'adresse mémoire. Vous ne pouvez pas supprimer un élément du tableau individuellement, vous pouvez seulement l'écraser.

Par exemple : je vous donne un tableau et une valeur val, et il vous est demandé de supprimer les éléments du tableau qui sont égaux à la valeur val. Comment faire ?

Idée 1 : Méthode brutale

Nous pouvons utiliser deux boucles for. Lors du passage vers un élément égal à la valeur val, déplacez l'intégralité de l'élément suivant vers l'avant pour couvrir l'élément à supprimer, mais cette approche prend évidemment du temps. la complexité est trop élevée.

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

Idée 2 : Méthode du double pointeur

Supposons un pointeur rapide et lent respectivement, lent et rapide, et que les deux se déplacent ensemble lorsque le pointeur lent rencontre l'élément à supprimer, il s'arrête et attend d'être supprimé (écrasé). ; lorsque le pointeur rapide Lorsque vous atteignez l'élément à gauche, attribuez l'élément du pointeur rapide au pointeur lent, puis les deux pointeurs reculent en même temps jusqu'à ce que le pointeur rapide parcoure tout le tableau.

Cela peut être compris comme ceci : définir la nouvelle longueur du tableau newLength, à partir de 0, définir un pointeur rapide pour parcourir le tableau rapidement, lorsque fast atteint l'élément à gauche, cela signifie que l'élément doit être ajouté à le nouveau tableau (c'est-à-dire être ajouté à l'indice newLength, cela équivaut à la partie du tableau avant que newLength soit considérée comme le nouveau tableau à renvoyer, ce qui équivaut à insérer des éléments dans ce nouveau tableau).

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

Questions recommandées

1. Supprimer les doublons dans les tableaux triés

2 Déplacer les zéros

3. Comparez les chaînes avec les espaces arrière

4. . Il ne s'agit que d'ajouter, de supprimer, de modifier et de vérifier des tableaux. Une fois que vous maîtrisez la recherche et la suppression de tableaux, vous pouvez commencer à répondre aux questions.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!