- 标签:数组、双指针、排序
- 难度:中等
描述:给定一个数组
要求:将数组进行排序,使得红色在前,白色在中间,蓝色在最后。
说明:
- 要求不使用标准库函数,同时仅用常数空间,一趟扫描解决。
-
$n == nums.length$ 。 -
$1 \le n \le 300$ 。 -
$nums[i]$ 为$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]
快速排序算法中的
这道题我们也可以借鉴快速排序算法中的
- 使用两个指针
$left$ 、$right$,分别指向数组的头尾。$left$ 表示当前处理好红色元素的尾部,$right$ 表示当前处理好蓝色的头部。 - 再使用一个下标
$index$ 遍历数组,如果遇到$nums[index] == 0$ ,就交换$nums[index]$ 和$nums[left]$ ,同时将$left$ 右移。如果遇到$nums[index] == 2$ ,就交换$nums[index]$ 和$nums[right]$ ,同时将$right$ 左移。 - 直到
$index$ 移动到$right$ 位置之后,停止遍历。遍历结束之后,此时$left$ 左侧都是红色,$right$ 右侧都是蓝色。
注意:移动的时候需要判断
class Solution:
def sortColors(self, nums: List[int]) -> None:
left = 0
right = len(nums) - 1
index = 0
while index <= right:
if index < left:
index += 1
elif nums[index] == 0:
nums[index], nums[left] = nums[left], nums[index]
left += 1
elif nums[index] == 2:
nums[index], nums[right] = nums[right], nums[index]
right -= 1
else:
index += 1
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(1)$。