Couleurs de tri du Leetcode

Intuition

L'intuition de base vient du tri.

Approche

Dans l'approche naïve, nous pouvons trier le tableau à l'aide de la fonction de tri intégrée. La complexité temporelle sera O(N*log(N)).

• Optimiser : Puisque nous ne trions que trois nombres, nous pouvons utiliser le concept de tri par comptage. Gardez une trace du nombre de zéros et du nombre de uns dans le tableau. # Complexité

• Complexité temporelle : O(N)

• Complexité spatiale : O(1)

Code

class Solution {
    public void sortColors(int[] nums) {
        int countZero = 0;
        int countOne  =  0;
        for(int num: nums){
            switch(num){
                case 0:
                    countZero++;
                    break;
                case 1:
                    countOne++;
            }
        }
        int currentIndex = -1;
        while(0<countZero--){
            nums[++currentIndex] = 0;
            // countZero--;
        }
        while(0<countOne--){
            nums[++currentIndex] = 1;
            // countOne--;
        }
        while(currentIndex<nums.length-1){
            nums[++currentIndex] = 2;
        }
    }
}

Repo GitHub pour plus de solutions : Git
Profil Leetcode : Leetcode : devn007

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!