leetcode 颜色分类_leetcode72

全栈程序员-站长 • 2022年8月8日下午4:16 • 未分类 • 阅读 9

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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

进阶：

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

题解

快排

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);
    }
};

因为只有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换到前面
        }
    }
};