leetcode 75. 颜色分类（medium）（优质解法）

链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

代码：

class Solution {
    public void sortColors(int[] nums) {
        int left=-1,right=nums.length,i=0;
        while(i<right){
            if(nums[i]==0){
                left++;
                swap(nums,left,i);
                i++;
            }else if(nums[i]==1){
                i++;
            }else{
                right--;
                swap(nums,right,i);
            }
        }
    }

    public void swap(int[] nums,int i,int j){
        int tmp=nums[i];
        nums[i]=nums[j];
        nums[j]=tmp;
    }
}

题解：

? ? ? ? 本题的含义很清晰，对于数组中 0，1，2 三种数据，我们要将其进行排序，如果用普通的排序方法来解决该题不是最好的办法

????????该题要把数组中的数据分为 3 个区间，分别是等于 0，1，2 的区间，我们可以通过定义两个指针来帮助划分区间，如下图所示：

? ? ? ? 其中 left 指针指向最后一个 0 的位置，right 指针指向第一个 2 的位置，i 指针用来遍历数组，划分遍历到的数据

? ? ? ? i 指针遍历数组时会遇到以下 3 种情况：

? ? ? ? （1）.nums[ i ] = 0 ,需要将 0 数据放到 [ 0,left ]，区间，所以需要先执行 left++，为 0 数据留出一个位置，交换 left 和 i 下标对应的数据，left ++ 以后指向的数据为 1，将 1 交换到 i 下标刚好放到了 1 区间，所以直接 i ++ 去处理下一个数据即可，依次要执行的代码是： left++ ，swap( ledt,i ) ,i++

? ? ? ? （2）.nums[ i ] = 1 ,由于 1 区间就在 i 下标之前，所以当前遍历到的数据 1 实际上就在 1 区间中，直接 i++ 即可

? ? ? ? （3）.nums[ i ] = 2,需要将 2 数据放到 [ right , nums.length-1] 区间，先让 right - - ，为 2 数据留出一个位置，交换 right 和 i 下标对应的数据，right - - 以后指向的数据是未处理的数据，该未处理的数据经过交换到达了 i 下标，所以此时还需要对 i 下标指向的数据进行处理，i 指针不能 ++，依次要执行的代码是：right - -，swap ( right , i ) ,

? ? ? ? 当 i = right 时就不存在未处理的数据了，处理完毕，划分结束