☆打卡算法☆LeetCode 75、颜色分类 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定包含红白蓝颜色的数组，对它们进行排序，使得相同颜色的元素相邻。”

题目链接：

来源：力扣（LeetCode）

链接：75. 颜色分类 - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

给定一个包含红色、白色和蓝色，一共 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]

二、解题

1、思路分析

这道题是经典的国旗问题，世界这么多国家画到地图上，相邻直接还不能相同颜色。

根据题意，可以考虑使用指针进行交换的方法。

可以考虑对数组进行两次遍历，第一次遍历将所有的0交换到数组的头部，第二次遍历将数组中所有的1换到头部的0之后，之后，所有的2就在数组的尾部了。

2、代码实现

代码参考：

public class Solution {
        public void SortColors(int[] nums)
        {
            int left = 0;
            int right = nums.Length - 1;

            //检查中间的颜色，如果有不是1的，则往边界外放
            for (int i = left; i <= right; i++)
            {
                if (left >= right)
                    break;
                if (nums[i] == 0)
                {
                    int a = nums[i];
                    int b = nums[left];
                    nums[i] = b;
                    nums[left] = a;
                    left++;
                    while (right > left)
                    {
                        if (nums[left] != 0)
                            break;
                        left++;
                    }
                    i = left;
                }
                if (nums[i] == 2)
                {
                    int a = nums[i];
                    int b = nums[right];
                    nums[i] = b;
                    nums[right] = a;
                    right--;
                    while (right > left)
                    {
                        if (nums[right] != 2)
                            break;
                        right--;
                    }
                    //如果换进去的是1，说明还要再换
                    if (a != 1 )
                        i--;
                }

            }
        }
}

3、时间复杂度

时间复杂度 ： O(n)

其中n是数组的长度，只需要遍历一遍数组即可求得答案。

空间复杂度： O(1)

只需要常数级别的空间存放变量。

三、总结

关键在于遍历边界内的数据时，如果换进来的数据不对。

还应当再判断一次，而不是往下继续走。