一、题目
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)
只需要常数级别的空间存放变量。
三、总结
关键在于遍历边界内的数据时，如果换进来的数据不对。
还应当再判断一次，而不是往下继续走。
