75.颜色分类

75.颜色分类

题解

题目：要求空间复杂度为O(1)

思路：

1. 单指针
2. 双指针
3. 三指针

代码

func sortColors(nums []int) {cnt := swap(nums, 0)swap(nums[cnt:], 1)
}
func swap(nums []int, target int) int {cnt := 0for i := 0; i < len(nums); i++ {if nums[i] == target {nums[cnt], nums[i] = nums[i], nums[cnt]cnt++}}return cnt
}

func sortColors(nums []int) {p0, p2 := 0, len(nums)-1for i := 0; i <= p2; i++ {for i <= p2 && nums[i] == 2 {nums[i], nums[p2] = nums[p2], nums[i]p2--}if nums[i] == 0 {nums[i], nums[p0] = nums[p0], nums[i]p0++}}
}

func sortColors(nums []int) {a, b, c := 0, 0, 0for _, v := range nums {if v == 0 {nums[c] = 2nums[b] = 1nums[a] = 0c++b++a++} else if v == 1 {nums[c] = 2nums[b] = 1c++b++} else if v == 2 {nums[c] = 2c++}}
}