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/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年4月18日 17:50
下一篇 2020年4月19日

相关推荐

  • leetcode80-删除排序数组中的重复项II

    原题 给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素最多出现两次,返回移除后数组的新长度。 不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外…

    算法 2020年5月26日
    0140
  • leetcode84-柱状图中最大的矩形

    原题 给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。 求在该柱状图中,能够勾勒出来的矩形的最大面积。 以上是柱状图的示例,其中每个柱子的宽…

    2020年1月24日
    0130
  • leetcode142-环形链表II

    原题 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始…

    2019年12月14日
    0440
  • leetcode279-完全平方数

    原题 给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, …)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 示例 1: 输入: n = 12 输出…

    2019年12月11日
    0150
  • leetcode112-路径总和

    原题 给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。 说明: 叶子节点是指没有子节点的节点。 示例:  给定如下二叉树,…

    算法 2020年1月12日
    0160
  • leetcode45-跳跃游戏II

    原题 原题 给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 示例: 输…

    算法 2020年2月15日
    0150
  • leetcode155-最小栈

    原题 设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。 push(x) – 将元素 x 推入栈中。 pop() – 删除栈顶的元素。 top() …

    算法 2019年12月11日
    0130
  • leetcode503-下一个更大元素II

    原题 给定一个循环数组(最后一个元素的下一个元素是数组的第一个元素),输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序,这个数字之后的第一个比它更大的数,…

    算法 2020年2月1日
    0110
  • leetcode234-回文链表

    原题 请判断一个链表是否为回文链表。 示例1: 输入: 1->2 输出: false 示例2: 输入: 1->2->2->1 输出: true 进阶: 你能否用 O(n) 时间复杂…

    2019年12月16日
    0120
  • leetcode202-快乐数

    原题 编写一个算法来判断一个数是不是“快乐数”。 一个“快乐数”定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是无…

    算法 2019年12月18日
    0120

发表回复

登录后才能评论