LeetCode75.颜色分类

题目链接：LeetCode75

题解

这道题两种做法，一种是用计数排序，因为告诉了你只有3种数字，所以直接创建一个长度为3的数组arr，然后遍历一遍原数组，每出现一次某个数，arr对应位置的值就加加。最后依次输出arr即可

代码

class Solution {
    public void sortColors(int[] nums) {
        int[] arr = new int[3];
        for(int i = 0;i < nums.length;i++) 
            arr[nums[i]]++;
        for(int i = 0,j = 0;i < 3;i++) {
            while((arr[i]--) != 0)
                nums[j++] = i;
        }
    }
}

还有一种方法，就是类似于快排的思想，将所有小于1的放左边，大于1的放右边

代码

class Solution {
    public void sortColors(int[] nums) {
        int l = 0;
        int r = nums.length - 1;
        int cur = 0;
        while(cur <= r) {
            if(1 < nums[cur])
                swap(nums,cur,r--);
            else if(1 > nums[cur])
                swap(nums,cur++,l++);
            else
                cur++;
        }
    }
    public void swap(int[] arr,int i,int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}