Problem: 75. 颜色分类

题目描述

思路及解法

由于题目只提供0，1，2分别代表颜色红、白、蓝，并按此排序，那么我们可以遍历两次数组，第一次将0，全部放到数组前面一部分，第二次将1全部放到0的后面（这些操作均可以通过交换数组中的元素实现）

复杂度

时间复杂度:

$O(n)$；其中$n$为数组的大小

空间复杂度:

$O(n)$

Code

class Solution {
    /**
     * Sort Colors
     *
     * @param nums Given array
     */
    public void sortColors(int[] nums) {
        int index = 0;
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[index];
                nums[index++] = temp;
            }
        }
        for (int i = index; i < nums.length; ++i) {
            if (nums[i] == 1) {
                int temp = nums[i];
                nums[i] = nums[index];
                nums[index++] = temp;
            }
        }
    }
}