LeetCode-75. Sort Colors

题目描述

给定一个由n个元素的数组，元素仅包含0，1，2三种形式，求数组排序的结果。不允许使用Arrays.sort()函数。

解题思路

1. 借鉴快排的思想，利用双指针从数组的左右两路扫描数组。满足left小于right，则开启总循环。如果右指针遇到2，则继续扫描right–；否则，停止扫描。如果左指针遇到2，则停止扫描，与右指针指向的元素做交换；如果左指针遇到1，将该位置添加到列表中，将继续扫描left++;如果左指针遇到0，判断列表是否为空（其实就是判断当前这个0的前面有没有1），为空继续扫描left++，反之两元素交换，继续扫描但是不执行left++（因为该位置为1，并且该位置后面有可能出现0，需要记录该位置，以备交换）。总循环结束后，需要判断临界点的情况，比如：输入1，0，0这种情况，总循环结束后，有可能right指向0，而且列表不为空，也就是说在该right位置之前有1存在，需要交换。
2. 可以将总循环的条件设置成left小于等于right，来避免最后一步的处理。

代码

public class Solution {
    public void sortColors(int[] nums) {
        if(nums==null || nums.length==0)
            return;
        int left=0;
        int right=nums.length-1;
        LinkedList<Integer> temList=new LinkedList<Integer>();
        int tem=0;
        while(left<=right){
            while(right>=left && nums[right]==2){
                right--;
            }
            while(left<=right && nums[left]<2){
                if(nums[left]==1){
                    temList.add(left);
                    left++;
                }else{
                    if(temList.size()!=0){
                    //这里不执行left++，如果执行了left++，该位置（元素值为1）就无法添加到列表中
                        nums[left]=1;
                        nums[temList.get(0)]=0;
                        temList.remove(0);
                    }else
                        left++;
                }

            }
            if(left<right){
                    tem=nums[right];
                    nums[right]=nums[left];
                    nums[left]=tem;
           }/*else if(temList.size()>0 && nums[right]==0){
                nums[right]=nums[temList.get(0)];
                nums[temList.get(0)]=0;
                //这里是left<right条件下，最后一步的判断
           }*/
        }
    }
}