Journal des problèmes de brosse à boutons de force / day6 / 6.28

Novice Village

Supprimer les éléments dupliqués d'un tableau ordonné,Aiguille à deux doigts

Cette méthode comporte deux exigences,Pour modifier sur la base du tableau original,Ne pas utiliser d'autres tableaux

Si la longueur du tableau est0;

Sortie directe

Si la longueur du tableau n'est pas0;

Définir deux pointeurs,fastEtslow,fastEtslowLa valeur initiale de1,Parce que pour comparerfastEtfast-1Éléments de

fastIndice utilisé pour traverser tous les éléments du tableau,slowUtilisé pour enregistrer le nombre d'éléments uniques

Quandfast-1EtfastLes éléments pointés ne sont pas les mêmes,Oui.fastLes éléments représentés sont donnés àslowÉléments représentés,Et va++slow,++fast

QuandfastEtfast-1Les éléments pointés sont les mêmes,++fast,slowSans changement

Par exemple, la figure ci - dessous,Quand le premier cycle commence,fast-=1,Éléments représentés0,Etfast-1Les éléments représentés sont les mêmes,En ce moment,fastContinuez à droite,slowSans changement.

 

fast=2Heure,L'élément pointé est1,Etfast-1Élément pointé0C'est différent.,À ce stade,fastÉlément pointé1ÀslowÉlément pointé,nums[slow]=nums[fast],Et vaslowÀ droite.,++slow,fastContinuez à droite,++fast

 

 

Continuez à avancer ......

Jusqu'àfast=9Heure（n=10,fast<n）,Oui.nums[9]Valeur attribuée ànums[4],++slow=5,À ce stade,nums[slow]Produits, Est un tableau qui élimine les éléments dupliqués .

slow C'est la longueur du nouveau tableau , Est modifié sur la base du tableau original .

Exemples

 Comment résoudre le problème：Comme ci - dessus

class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if (n == 0) {    // Déterminer si la longueur du tableau est 0
            return 0;
        }
        int fast = 1, slow = 1;    // Réglage de deux pointeurs rapides et lents 
        while (fast < n) {        //La longueur du tableau estn, Donc l'emplacement de l'élément à la fin est n-1
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                ++slow;    // Enfin, la longueur du tableau sans duplication doit être sortie ,Alors choisissez++slow
            }
            ++fast;    // Empêcher l'entrée illégale dans la boucle 
        }
        return slow;    // Renvoie la longueur du tableau sans répétition 
    }
}

Autres idées ：

foreachTraversée (for Chaque)

jdk5.0Nouvelles caractéristiques,NouveauforCycle

for(type x:type Y)

TraverséeTableau ou collectionYÉléments de, Chaque traversée assigne la valeur de l'élément à x

Par exemple

for(int num:nums)

C'est ça.nums Ce tableau traverse , Combien de numéros , Combien de fois .

Donnez une de ces valeurs à chaque fois que vous traversez num;

foreachPeut être utiliséforSubstitution de déclarations

for(int i =0;i<nums.length;i++){

    System.out.print(nums[i]+" ");

}

Idées générales：

 

class Solution {
    public int removeDuplicates(int[] nums) {   
        return process(nums, 1);
    }
    int process(int[] nums, int k) {
        int idx = 0; 
        for (int x : nums) {
            if (idx < k || nums[idx - k] != x) nums[idx++] = x;
        }
        return idx;
    }
}

Les deux dernières idées sont citées leetcode Contenu du blogueur shanggongshui sanye ,En cas d'infraction,Contact supprimer