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中文网其他相关文章！