各位如果看到博客内有广告,可以动手点一点,谢谢

MENU

LeetCode75.颜色分类

August 7, 2018 • Read: 365 • LeetCode

题目链接: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;
    }
}
Archives Tip
QR Code for this page
Tipping QR Code