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日

相关推荐

  • leetcode496-下一个更大元素I

    原题 给定两个没有重复元素的数组 nums1 和 nums2 ,其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。 nums…

    算法 2020年1月31日
    0380
  • leetcode100-相同的树

    原题 给定两个二叉树,编写一个函数来检验它们是否相同。 如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。 示例 1: 输入: 1 1 / \ / \ 2 3 2 …

    算法 2020年5月7日
    0180
  • leetcode57-插入区间

    原题 给出一个无重叠的 ,按照区间起始端点排序的区间列表。 在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。 示例 1: 输入: …

    算法 2020年5月12日
    0270
  • leetcode560-和为K的子数组

    原题 给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。 示例 1: 输入: nums = [1,1,1], k = 2 输出: 2 , [1,1]…

    算法 2020年5月15日
    0460
  • leetcode313-超级丑数

    原题 编写一段程序来查找第 n 个超级丑数。 超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。 示例: 输入: n = 12, primes = [2…

    算法 2020年2月11日
    0100
  • leetcode144-二叉树的前序遍历

    原题 给定一个二叉树,返回它的 前序 遍历。 示例: 输入: [1,null,2,3]  1   \    2 &nbs…

    算法 2020年1月10日
    0120
  • leetcode31-下一个排列

    原题 整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。 例如,arr = [1,2,3] ,以下这些都可以视作 arr 的排列:[1,2,3]、[1,3,2]、[3,1…

    算法 2022年4月13日
    02363
  • leetcode200-岛屿数量

    原题 给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水…

    算法 2019年11月24日
    0130
  • leetcode134-加油站

    原题 在一条环路上有 N 个加油站,其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[…

    算法 2020年2月16日
    080
  • leetcode110-平衡二叉树

    原题 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 示例 1:  给定二叉树 […

    算法 2020年1月17日
    0170

发表回复

登录后才能评论