leetcode 颜色分类_LEETCODE

leetcode 颜色分类_LEETCODE给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。示例 1:输入:nums = [2,0,2,1,1,0]输出:[0,0,1,1,2,2]示例 2:输入:nums = [2,0,1]输出:[0,1,2]示例 3:输入:nums = [0]输出:[0]示例 4:输入:nums = [1]输出:[1] 提示:n == num

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

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

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

示例 1:

输入:nums = [2,0,2,1,1,0]
输出:[0,0,1,1,2,2]
示例 2:

输入:nums = [2,0,1]
输出:[0,1,2]
示例 3:

输入:nums = [0]
输出:[0]
示例 4:

输入:nums = [1]
输出:[1]
 

提示:

n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2
 

进阶:

你可以不使用代码库中的排序函数来解决这道题吗?
你能想出一个仅使用常数空间的一趟扫描算法吗?

题解

  1. 快排
class Solution { 
   
public:
    void quick(int l,int r,vector<int>& nums){ 
   
        if(l < r){ 
   
            int mid = partion(l,r,nums);
            quick(l,mid - 1,nums);
            quick(mid + 1,r,nums);
        }
    }
    int partion(int l,int r,vector<int>&nums){ 
   
        int key = nums[l];
        while(l < r){ 
   
            while(l < r && nums[r] > key)r --;
            if(l < r)nums[l ++] = nums[r];
            while(l < r && nums[l] < key)l ++;
            if(l < r)nums[r --] = nums[l];
        }
        nums[l] = key;
        return l;
    }
    void sortColors(vector<int>& nums) { 
   
        int l = 0,r = nums.size() - 1;
        quick(l,r,nums);
    }
};
  1. 因为只有3组数字,最左边有一组,最右边有一组,中间有一组,所以把最左边和最右边都规整后,中间自然就规整,所以设置i,j代表左边放置0的下边,j为右边放置2的下标.

时间复杂度O(n)

class Solution { 
   
public:
    void sortColors(vector<int>& nums) { 
   
        int i = 0,n = nums.size(),j = nums.size() - 1;
        while(i < n && nums[i] == 0)i ++;
        while(j >= 0 && nums[j] == 2)j --;
        for(int k = i;k <= j;k ++){ 
   
            if(nums[k] == 0)swap(nums[i],nums[k]),i ++;
            else if(nums[k] == 2)swap(nums[j],nums[k]),k --,j --;   //注意当从后面换回去的时候可能回把后面的0换到前面
        }
    }
};
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/169157.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • ByteBuffer详解「建议收藏」

    ByteBuffer详解「建议收藏」一、前言前一篇文章我们介绍了Android中直播视频技术的基础大纲知识,这里就开始一一讲解各个知识点,首先主要来看一下视频直播中的一个重要的基础核心类:ByteBuffer,这个类看上去都知道了,是字节缓冲区处理字节的,这个类的功能非常强大,也在各个场景都有用到,比如网络数据底层处理,特别是结合网络通道信息处理的时候,还有就是后面要说到的OpenGL技术也要用到,当然在视频处理中也是很重要

  • swing58_ML2437A

    swing58_ML2437A给定一个长度为 n 的整数序列,初始时序列为 {1,2,…,n−1,n}。序列中的位置从左到右依次标号为 1∼n。我们用 [l,r] 来表示从位置 l 到位置 r 之间(包括两端点)的所有数字构成的子序列。现在要对该序列进行 m 次操作,每次操作选定一个子序列 [l,r],并将该子序列中的所有数字进行翻转。例如,对于现有序列 1 3 2 4 6 5 7,如果某次操作选定翻转子序列为 [3,6],那么经过这次操作后序列变为 1 3 5 6 4 2 7。请你求出经过 m 次操作后的序列。输入格式第

  • 一个简洁的PHP可逆加密函数(分享)

    一个简洁的PHP可逆加密函数(分享)

    2021年10月12日
  • 内外网同时使用route add

    内外网同时使用route add使用routeadd添加路由,使两个网卡同时访问内外网routeadd命令格式:route[-f][-p][Command][Destination][maskNetmask][Gateway][metricMetric][ifInterface] 通过配置电脑的静态路由来实现同时访问内外网的。电脑的网络IP配置不用变,两个网卡都按照正常配置(都配置IP地址、子网掩码、网…

  • 4月20日

    4月20日

  • idea 2021激活码【永久激活】

    (idea 2021激活码)最近有小伙伴私信我,问我这边有没有免费的intellijIdea的激活码,然后我将全栈君台教程分享给他了。激活成功之后他一直表示感谢,哈哈~IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.htmlWK…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号