“给定包含红白蓝颜色的数组,对它们进行排序,使得相同颜色的元素相邻。”
题目链接:
来源:力扣(LeetCode)
链接:75. 颜色分类 - 力扣(LeetCode) (leetcode-cn.com)
给定一个包含红色、白色和蓝色,一共 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]
这道题是经典的国旗问题,世界这么多国家画到地图上,相邻直接还不能相同颜色。
根据题意,可以考虑使用指针进行交换的方法。
可以考虑对数组进行两次遍历,第一次遍历将所有的0交换到数组的头部,第二次遍历将数组中所有的1换到头部的0之后,之后,所有的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--;
}
}
}
}
时间复杂度 : O(n)
其中n是数组的长度,只需要遍历一遍数组即可求得答案。
空间复杂度: O(1)
只需要常数级别的空间存放变量。
关键在于遍历边界内的数据时,如果换进来的数据不对。
还应当再判断一次,而不是往下继续走。