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)


相关推荐

发表回复

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

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