title	tags	author	description
0075.Sort Colors	Medium, Sort	Kimi Tsai <kimi0230@gmail.com>

75. Sort Colors

题目

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library's sort function for this problem.

Example 1:

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Follow up:

A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
Could you come up with a one-pass algorithm using only constant space?

給定一個包含紅色、白色和藍色，一共 n 個元素的數組，原地對它們進行排序，使得相同顏色的元素相鄰，並按照紅色、白色、藍色順序排列。

此題中，我們使用整數 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]

範例 3：

輸入：nums = [0]
輸出：[0]

範例 4：

輸入：nums = [1]
輸出：[1]

提示：

n == nums.length
1 <= n <= 300
nums[i] 為 0、1 或 2

進階：

你可以不使用代碼庫中的排序函數來解決這道題嗎？
你能想出一個僅使用常數空間的一趟掃描算法嗎？

來源：力扣（LeetCode）鏈接：https://leetcode-cn.com/problems/sort-colors 著作權歸領扣網絡所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。

題目大意

抽象題意其實就是排序。這題可以用快排一次通過。

解題思路

題目末尾的 Follow up 提出了一個更高的要求，能否用一次循環解決問題？這題由於數字只會出現 0，1，2 這三個數字，所以用游標移動來控制順序也是可以的。具體做法：0 是排在最前面的，所以只要添加一個 0，就需要放置 1 和 2。1 排在 2 前面，所以添加 1 的時候也需要放置 2 。至於最後的 2，只用移動游標即可。

這道題可以用計數排序，適合待排序數字很少的題目。用一個 3 個容量的數組分別計數，記錄 0，1，2 出現的個數。然後再根據個數排列 0，1，2 即可。時間複雜度 O(n)，空間複雜度 O(K)。這一題 K = 3。

這道題也可以用一次三路快排。數組分為 3 部分，第一個部分都是 0，中間部分都是 1，最後部分都是 2 。

來源

解答

https://github.com/kimi0230/LeetcodeGolang/blob/master/Leetcode/0075.Sort-Colors/0075.Sort-Colors.go

package sortcolors

func sortColors(nums []int) {
	if len(nums) == 0 {
		return
	}

	var index0, index1, index2 = 0, 0, 0
	for _, num := range nums {
		switch num {
		case 0:
			nums[index2] = 2
			index2++
			nums[index1] = 1
			index1++
			nums[index0] = 0
			index0++
		case 1:
			nums[index2] = 2
			index2++
			nums[index1] = 1
			index1++
		case 2:
			index2++
		}
	}
}

/*
二路快排與三路快排
先掌握二路快排， https://leetcode-cn.com/problems/sort-an-array/solution/golang-er-lu-kuai-pai-by-rqb-2/
三路快排稍微改下即可

區別：
二路快排，分兩部分：小於等於、大於二部分。
三路快排分為，小於、等於、大於三部分。

三路快排：
相比二路快排增加一個變量記錄相等的起始元素。
假設選擇數組第一個元素作為參考元素。則起始下邊為0，即為equalHead

作者：hibrq
链接：https://leetcode-cn.com/problems/sort-an-array/solution/golang-san-lu-kuai-pai-by-rqb-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/
func sortColorsQuickSort(nums []int) {
	if len(nums) < 2 {
		return
	}

	pivot := nums[0]

	head, tail := 0, len(nums)-1
	i := 1
	equalHead := 0
	for head < tail {
		if nums[i] < pivot {
			nums[i], nums[equalHead] = nums[equalHead], nums[i]
			head++
			i++
			equalHead++
		} else if nums[i] == pivot {
			i++
			head++
		} else {
			nums[i], nums[tail] = nums[tail], nums[i]
			tail--
		}
	}
	sortColorsQuickSort(nums[:equalHead])
	sortColorsQuickSort(nums[tail+1:])
}