算法leetcode｜75. 颜色分类（rust重拳出击）

文章目录

75. 颜色分类：

给定一个包含红色、白色和蓝色、共

n

个元素的数组

nums

，

原地

对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数

0

、

1

和

2

分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

样例 1：

输入：
    
    nums = [2,0,2,1,1,0]
    
输出：
    
    [0,0,1,1,2,2]

样例 2：

输入：
    
    nums = [2,0,1]
    
输出：
    
    [0,1,2]

提示：

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

分析：

• 面对这道算法题目，二当家的再次陷入了沉思。
• 感觉最直观的方式就是两次遍历，先从左到右遍历把红色都换到左边，再从右到左遍历把蓝色都换到右面，常数级的额外空间，O(n) 的时间复杂度，已经很优秀了吧，还要什么自行车，要什么手表，这么简单易懂。
• 但是算法就是要尽可能优化啊，没错，我们遍历了两次，能不能只遍历一次呢？
• 那就必须在一次遍历中同时将红色换到左边，并且把蓝色换到右面，有什么好的办法吗？注意到一个细节，题目中要求不能用内置的排序，为什么呢？优秀的排序算法的时间复杂度也要到 O(n*log n) 啊，还不如两次遍历呢，什么鬼？突然我转念一想，一般内置的排序算法都是 快速排序，然后想到快速排序中的一个片段，就是找到一个基准数，然后将小于基准数的元素都移动到基准数的左边，大于基准数的元素都移动到基准数的右边，怎么样，是不是豁然开朗？这不就是答案吗？
• 使用双指针分别放在头尾表示红色和蓝色的边界，然后遍历元素，如果是红色就交换到左边红色的边界并且移动这个红色的边界，如果是蓝色就交换到右边蓝色的边界并且移动这个蓝色的边界，如果是白色就不做处理继续遍历下一个元素。

题解：

rust：

implSolution{pubfnsort_colors(nums:&mutVec<i32>){let(mut i,mut l,mut r)=(0,0, nums.len()-1);while i <= r {if nums[i]<1{if i == l {
                    i +=1;}else{
                    nums.swap(i, l);}
                l +=1;}elseif nums[i]>1{if i == r {break;}
                nums.swap(i, r);
                r -=1;}else{
                i +=1;}}}}

go：

funcsortColors(nums []int){
    i, l, r :=0,0,len(nums)-1for i <= r {if nums[i]<1{if i == l {
                i++}else{
                nums[i], nums[l]= nums[l], nums[i]}
            l++}elseif nums[i]>1{if i == r {break}
            nums[i], nums[r]= nums[r], nums[i]
            r--}else{
            i++}}}

c++：

classSolution{public:voidsortColors(vector<int>& nums){int i =0, l =0, r = nums.size()-1;while(i <= r){if(nums[i]<1){if(i == l){++i;}else{swap(nums[i], nums[l]);}++l;}elseif(nums[i]>1){if(i == r){break;}swap(nums[i], nums[r]);--r;}else{++i;}}}};

python：

classSolution:defsortColors(self, nums: List[int])->None:"""
        Do not return anything, modify nums in-place instead.
        """
        i, l, r =0,0,len(nums)-1while i <= r:if nums[i]<1:if i == l:
                    i +=1else:
                    nums[i], nums[l]= nums[l], nums[i]
                l +=1elif nums[i]>1:if i == r:break
                nums[i], nums[r]= nums[r], nums[i]
                r -=1else:
                i +=1

java：

classSolution{publicvoidsortColors(int[] nums){int i =0, l =0, r = nums.length -1;while(i <= r){if(nums[i]<1){if(i == l){++i;}else{int t = nums[i];
                    nums[i]= nums[l];
                    nums[l]= t;}++l;}elseif(nums[i]>1){if(i == r){break;}int t = nums[i];
                nums[i]= nums[r];
                nums[r]= t;--r;}else{++i;}}}}

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】三连走一波~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~