荷兰国旗问题 之 指针划分区间问题

• 首先介绍一下什么是荷兰国旗问题？
• 问题描述为：给定一个由红色、白色和蓝色三种颜色组成的无序数组，将数组元素按颜色排序，使得所有红色元素在前，白色元素居中，蓝色元素在后。这里的 “颜色” 通常用数字 0（红色）、1（白色）、2（蓝色） 表示，因此问题也等价于将数组中的 0、1、2 排序，使得所有 0 在前，1 居中，2 在后。
• 当然这个问题，常常要求使用o(n)的时间复杂度进行求解

指针划分区间

• 对于原地修改的操作，我们有两个思路，一个是单指针，两次遍历，另一个是双指针，单次遍历
  • 单指针，两次遍历：首先在第一次遍历中，我们定义变量ptr为区间0的右边界(也就是下一个0的位置)，然后遍历ptr右边的位置，当遇到0的时候，就执行nums[i]和nums[ptr]互换位置，然后ptr+=1，在第二次遍历的时候，我们从range(ptr,n)开始遍历，当遇到1的时候就执行类似的操作即可
  • 双指针，单次遍历：定义p0,p1分别为区间0和区间1的右边界，然后当遇到1的时候，我们只需交换nums[i]和nums[p1]，然后p1+=1,如果遇到的是0，我们需要执行交换nums[i]和nums[p0]，并且还要判断p0是否小于p1，因为如果小于的话，说明二者有重叠，所以刚刚交换出去的nums[p0]就会是1，所以需要考虑交换回来，还需要执行交换nums[i]和nums[p1]，然后p1+=1,p0+=1

75.颜色分类

• 思路分析：

单指针，两次遍历

class Solution:def sortColors(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""# 使用单指针，两次遍历ptr = 0 n = len(nums)for i in range(n):if nums[i] == 0:nums[ptr],nums[i] = nums[i],nums[ptr]ptr += 1for i in range(ptr,n):if nums[i] == 1:nums[ptr],nums[i] = nums[i],nums[ptr]ptr += 1

双指针，单次遍历

class Solution:def sortColors(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""# 使用双指针，单次遍历p0,p1 = 0,0 n = len(nums)for i in range(n):if nums[i] == 0:nums[i],nums[p0] = nums[p0],nums[i]if p0 < p1:nums[p1],nums[i] = nums[i],nums[p1]p0 += 1p1 += 1elif nums[i] == 1:nums[i],nums[p1] = nums[p1],nums[i]p1 += 1