讨论/《数组类算法》 - 颜色分类/
《数组类算法》 - 颜色分类

使用左右快慢指针方法,从左至右遍历一遍数组,如果为0则根据左边的慢指针存储,左边慢指针往右移动,快指针i加1,如果为2则根据右边慢指针存储,然后右边慢指针往左移动,需要注意的是右边慢指针移动后快指针i不能加1了,因为左右交换后还得对快指针i的数进行判断,如果为1则不管,直接i++就可以了,终止条件为快指针i<=右边慢指针就可以了。
代码如下:

class Solution {
    public void sortColors(int[] nums) {
        int n=nums.length;
        int left=0;
        int ens=n-1;
        int i=0;
        while(i<=ens)
        {
            if(nums[i]==0)
            {
                int temp=nums[left];
                nums[left]=nums[i];
                nums[i]=temp;
                left++;
                i++;
            }
            else if(nums[i]==2)
            {
                int temp=nums[ens];
                nums[ens]=nums[i];
                nums[i]=temp;
                ens--;
            }
            else
            {
                i++;
            }

        }

    }
}
1
展开全部 30 讨论