题目描述
Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.
We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.
You must solve this problem without using the library’s sort function.
Example 1:
Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Example 2:
Input: nums = [2,0,1]
Output: [0,1,2]
Example 3:
Input: nums = [0]
Output: [0]
Example 4:
Input: nums = [1]
Output: [1]
Constraints:
- n == nums.length
- 1 <= n <= 300
- nums[i] is 0, 1, or 2.
Follow up: Could you come up with a one-pass algorithm using only constant extra space?
题目分析
题目要求使用常量额外空间的条件下，进行一次遍历即完成排序。
由于数组组成元素只有0，1，2；假设数组为[2, 1, 0]，那么我们需要考虑一种方式，将元素0移动到数组的开头，2移动到数组的末尾，那么显然对于这个简单的数组交换0和2即可满足。
以此扩展思路，我们使用双指针方式进行求解，具体的思路见代码注释
示例代码
// 利用左右指针解决，左指针指向排序后的最后1个0的后1个位置；右指针指向排序后的第一个2的前1个位置
// 遍历数组，当遇到0时，当前指针与左指针交换，相当于把 0 append在头部连续的0之后
// 当遇到2时， 当前指针数据与右指针交换，相当于把 2 append在尾部连续的2之前
func sortColors(nums []int) {
if len(nums) <= 1 {
return
}
// 左右指针
left, right := 0, len(nums)-1
for i := 0; i < len(nums); i++ {
// i超过right，说明排序已经完成
if i > right {
break
}
if nums[i] == 0 {
nums[left], nums[i] = nums[i], nums[left]
// 当前left指向已经变为0，left往右移动一位
left++
// 这里不需要进行i--是因为:
// 由于i与left初始都为0，遍历过程中，必定有i >= left; left指向的不可能为2；只可能为0或者1
// (假如left指向的为2，由于i>=left，那么left指向的元素必定已经被排序过，那么2会被移动至right位置；与left指向为2矛盾，故left指向的只可能是0或者1)
continue
}
if nums[i] == 2 {
nums[i], nums[right] = nums[right], nums[i]
// 当前right指向已经变为2，right往左移动一位
right--
// 注意这里，如果i指向的值为1，那么下一轮循环无需处理；
// 如果值为0，那么需要再和left比较一次
// 因此，这里需要对i--，让下一轮循环再次check i
i--
continue
}
}
}