leetcode75-颜色分类

原题

给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:
不能使用代码库中的排序函数来解决这道题。

示例:

输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2]

进阶:

  • 一个直观的解决方案是使用计数排序的两趟扫描算法。
    首先,迭代计算出0、1 和 2 元素的个数,然后按照0、1、2的排序,重写当前数组。
  • 你能想出一个仅使用常数空间的一趟扫描算法吗?

解法

思想

计数排序算是这类问题的通解吧。。不过对于仅有两种或三种元素,可以使用交换方法来解。

代码

计数:

class Solution {
    public void sortColors(int[] nums) {
        int count0 = 0,count1 = 0,count2 = 0;
        for(int i:nums){
            if(i == 0) count0++;
            else if(i == 1) count1++;
            else count2++;
        }
        for(int i = 0;i<nums.length;i++){
            if(i<count0) nums[i] = 0;
            else if(i<count0+count1) nums[i] = 1;
            else nums[i] = 2;
        }
    }
}

三指针交换:

class Solution {
    public void sortColors(int[] nums) {
        int p0 = 0, cur = 0;
        int p2 = nums.length - 1;

        int tmp;
        while (cur <= p2) {
            if (nums[cur] == 0) {
                tmp = nums[p0];
                nums[p0++] = nums[cur];
                nums[cur++] = tmp;
            }
            else if (nums[cur] == 2) {
                tmp = nums[cur];
                nums[cur] = nums[p2];
                nums[p2--] = tmp;
            }
            else cur++;
        }
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode75-%e9%a2%9c%e8%89%b2%e5%88%86%e7%b1%bb/

发表评论

电子邮件地址不会被公开。