Problem: 75. 颜色分类

思路

解题方法

描述你的解题方法

复杂度

时间复杂度: $O(n)$

空间复杂度: $O(1)$

Code

class Solution {
public void sortColors(int[] nums)
	{
		int n = nums.length;
		int p0 = 0;// 当前已知的最后一个0在数组中的下标（0元素的个数）
		int p2 = n - 1;
		for (int i = 0; i <= p2; i++)
		{
			while (i <= p2 && nums[i] == 2)
			{
//				nums[i] 与 nums[p2] 交换，即把 2 放到后面
				int t = nums[i];
				nums[i] = nums[p2];
				nums[p2] = t;
				p2--;
			}
			if (nums[i] == 0)
			{
//				nums[i] 与 nums[p0] 交换，即把 0 放到后面
				int t = nums[i];
				nums[i] = nums[p0];
				nums[p0] = t;
				p0++;
			}
		}
	}
}

💖 超简洁版

👨‍🏫 参考题解

class Solution {
    public void sortColors(int[] nums) {
        int n0 = 0, n1 = 0;
        for(int i = 0; i < nums.length; i++){
            int num = nums[i];
            nums[i] = 2;
            if(num < 2){
                nums[n1++] = 1;
            }
            if(num < 1){
                nums[n0++] = 0;
            }
        }
    }
}