Leetcode ソートカラー

直感

基本的な直感は並べ替えから生まれます。

アプローチ

単純なアプローチでは、組み込みのソート関数を使用して配列をソートできます。時間計算量は O(N*log(N)) になります。

• 最適化: 3 つの数値のみをソートしているため、カウントソートの概念を使用できます。配列内の 0 の数と 1 の数を追跡します。 # 複雑さ

• 時間計算量: O(N)

• 空間複雑さ: O(1)

コード

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

その他のソリューションの GitHub リポジトリ: Git
リートコード プロフィール: リートコード: devn007

以上がLeetcode ソートカラーの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。