Leetcode 排序顏色

直覺

基本直覺來自排序。

方法

在簡單的方法中，我們可以使用內建的排序函數對陣列進行排序。時間複雜度為 O(N*log(N))。

• 最佳化： 由於我們只對三個數字進行排序，因此我們可以使用計數排序的概念。追蹤數組中 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
Leetcode簡介：Leetcode：devn007

以上是Leetcode 排序顏色的詳細內容。更多資訊請關注PHP中文網其他相關文章！