LeetCode75. 颜色分类

LeetCode75. 颜色分类

题目说明

/**
     * 
     * 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，
     * 原地对它们进行排序，使得相同颜色的元素相邻，
     * 并按照红色、白色、蓝色顺序排列。
     * <p>
     * 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
     */

思路分析

1. 数组中只有0，1，2三种数字，代表三种颜色,类似于对这三种数字的从小到大排序
2. 可以使用扫描的方法，先扫描数组将所有的零全部移动到数组的前面
3. 再扫描一次将所有的1放置到0的后面
4. 则剩下的2不用再处理，已经在数组的末尾
5. 源码见下

源码及分析

/**
     *
     * @param nums 要排序的数组
     */
    public void sortColors(int[] nums) {
        //定义变量index为处理后的数组索引
        int index = 0, tmp = 0;
        //第一次遍历将所有的0全部移动到最前面
        for (int i = 0; i < nums.length; i++) {
            //如果是0，则交换位置
            if (nums[i] == 0){
                tmp = nums[index];
                nums[index] = nums[i];
                nums[i] = tmp;
                index++;
            }
        }
        //index之前的数组元素已经处理完毕，全部为0，从index往后扫描
        for (int i = index; i < nums.length; i++) {
            if (nums[i] == 1){
                tmp = nums[index];
                nums[index] = nums[i];
                nums[i] = tmp;
                index++;
            }
        }
        //将1处理完毕后剩下的就是2
    }

LeetCode75. 颜色分类

原文：https://www.cnblogs.com/mx-info/p/14874289.html