75.颜色分类
75.颜色分类
题解
题目：要求空间复杂度为O(1)
思路：
- 单指针
- 双指针
- 三指针
代码
func sortColors(nums []int) { cnt := swap(nums, 0) swap(nums[cnt:], 1) } func swap(nums []int, target int) int { cnt := 0 for 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)-1 for 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, 0 for _, v := range nums { if v == 0 { nums[c] = 2 nums[b] = 1 nums[a] = 0 c++ b++ a++ } else if v == 1 { nums[c] = 2 nums[b] = 1 c++ b++ } else if v == 2 { nums[c] = 2 c++ } } }
