75.M 颜色分类

Problem: 75. 颜色分类

思路

思路1：单指针 先让pos指向需要被替换的位置，然后分两轮遍历：

• 第一轮：从pos开始遍历，发现0后，把当前位置与pos交换，同时让pos指向下一个位置

• 第二轮：从pos开始遍历，发现1后，把当前位置与pos交换，同时让pos指向下一个位置

思路2：三指针

• left指针指向下一个应该放0的位置

• right指针指向下一个应该放2的位置

• mid从left开始往后遍历：

  • 如果遇到了0，那就跟left位置交换，left++, mid++

  • 如果遇到了2，那就跟right交换位置，right--

  • 否则，mid++

Code

代码1：

func sortColors(nums []int) {
	pos := 0
	for i := pos; i < len(nums); i++ {
		if nums[i] == 0 {
			nums[pos], nums[i] = nums[i], nums[pos]
			pos++
		}
	}

	for i := pos; i < len(nums); i++ {
		if nums[i] == 1 {
			nums[pos], nums[i] = nums[i], nums[pos]
			pos++
		}
	}
}

代码2：

func sortColors(nums []int) {
	left, mid, right := 0, 0, len(nums)-1
	for mid <= right {
		if nums[mid] == 0 {
			nums[left], nums[mid] = nums[mid], nums[left]
			left++
			mid++
		} else if nums[mid] == 2 {
			nums[mid], nums[right] = nums[right], nums[mid]
			right--
			//该分支不能确定交换过来的right位置的值是什么，所以需要下一轮继续检查
		} else {
			mid++
		}
	}
}