75. 颜色分类

leetcode链接：
https://leetcode.cn/problems/sort-colors/description/

方案一

统计个数，然后编排

int red = 0,white = 0;
for (int i = 0; i < nums.length; i++) {
	if (nums[i] == 0) {
		red++;
	} else if (nums[i] == 1) {
		white++;
	}
}

for (int i = 0; i < red; i++) {
	nums[i] = 0;
}
for (int i = red; i < red + white; i++) {
	nums[i] = 1;
}
for (int i = red + white; i < nums.length; i++) {
	nums[i] = 2;
}

结果：

• 87/87 cases passed (0 ms)
• Your runtime beats 100 % of java submissions
• Your memory usage beats 23.55 % of java submissions (40.2 MB)

分析：
时间复杂度 2n –> n
空间复杂度 常数

方案二

循环一次执行完成 <– 伪一次，极端情况还是两次，就当一次思考方法了

参考 LeetCode官方题解 其中的方法二思路相似，其使用了交换元素的方式，所以只需要一次循环。

int red = 0, white = 0;

for (int i = 0; i < nums.length; i++) {
	if (nums[i] == 0) {
		nums[red] = 0;
		if (red != white)
			nums[white] = 1;
		red++;
		white++;
	} else if (nums[i] == 1) {
		nums[white] = 1;
		white++;
	}
}
for (int i = white; i < nums.length; i++) {
	nums[i] = 2;
}

结果：

• 87/87 cases passed (0 ms)
• Your runtime beats 100 % of java submissions
• Your memory usage beats 46.48 % of java submissions (40 MB)

几乎最优方案

https://leetcode.cn/problems/sort-colors/solution/yan-se-fen-lei-by-leetcode-solution/

与方案二思路差不多，但是双指针一个指向数组最前面，一个指向数组最后面

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        int p0 = 0, p2 = n - 1;
        for (int i = 0; i <= p2; ++i) {
            while (i <= p2 && nums[i] == 2) {
                int temp = nums[i];
                nums[i] = nums[p2];
                nums[p2] = temp;
                --p2;
            }
            if (nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[p0];
                nums[p0] = temp;
                ++p0;
            }
        }
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/sort-colors/solution/yan-se-fen-lei-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。