未分類

Sort Colors

Array, Go, LeetCode, Sort, TwoPointers

Sort Colors

Given an array with n objects colored red, white or blue, sort them 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.

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 an one-pass algorithm using only constant space?

提示 解題應用
Array Array/Slice
TwoPointers 紀錄index位置

Default:

1
2
3
func sortColors(nums []int)  {
}

解答思路:

一開始看到直接用氣泡排序就完成了，然而用排序的方式來解此題會浪費不少時間，因為陣列中的所有元素只由三個不同的數字所組成，再加上又知道是哪三個數字的前提之下就應該要有更好的方式來善用這些已知道的資訊，在Follow up中有提到遍歷兩次就可以解決，第一次是紀鍵三個不同的數字0,1,2分別有多少個(是我會用hashmap來儲存)，第二次就是根據次數由三個數字小至大直接取代掉整個陣列，然而其實有更佳的方法就是只遍歷一次的情況下便可以搞定，概念上其實不會差太多，就是想辦法一邊遍歷取代一邊紀錄次數(更準確的說法是紀錄位置)，先試想有三個變數來紀錄0,1,2在排序後陣列上最後一個值的位置(一開始index都為0)，當在遍歷尚未排序的陣列時，如果出現0除了要將0紀錄的位置向後推，連同1、2也要向後推(因為0在最前面)，出現1除了要將1紀錄的位置向後推，連2也要向後推，而出現2就只有2紀錄的位置向後推就好，因為2後頭沒有其它數字，因此不會影響其它數字的位置，待遍歷結束後三個變數就已經分別代表0,1,2在排序後陣列上最後一個值的位置，最後再想一想如果一邊在將位置後推的同時一邊取代一路上的值，先是2後推的同時將一路上的值轉為2到陣列底，接著是1後推的同時將一路上的值轉為1到最後一個值的位置(將部分才剛取代為2的值取代為1)，再來才是0後推的同時將一路上的值轉為0到最後一個值的位置(將部分才剛取代為1的值取代為0)，如此一來三個變數所紀錄0,1,2的位置在分別到達最後一個值位置的同時也排序完整個陣列了。

程式碼解說:

因為要紀錄下0,1,2在排序後陣列上最後一個值的位置，所以就先初始化三個變數來分別代表目前最後一個值的位置，接著就是開始遍歷尚未排序的陣列，如果取出的值為0就將0,1,2紀錄的位置向後推，同時先由2開始取代一路上的值(取代最後一個值所在的該位置)，接著才換1取代，再來才是換0取代，而取出的值為1則是將1,2的位置向後推，也是先由2開始取代接著才輪到1，最後如果取出的值為2就只將2的位置向後推，並只以2取代一路上的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
zero := 0
one := 0
two := 0
for _, v := range nums {
	if v == 0 {
		nums[two] = 2
		nums[one] = 1
		nums[zero] = 0
		two++
		one++
		zero++
	} else if v == 1 {
		nums[two] = 2
		nums[one] = 1
		two++
		one++
	} else {
		nums[two] = 2
		two++
	}
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func sortColors(nums []int) {
	zero := 0
	one := 0
	two := 0
	for _, v := range nums {
		if v == 0 {
			nums[two] = 2
			nums[one] = 1
			nums[zero] = 0
			two++
			one++
			zero++
		} else if v == 1 {
			nums[two] = 2
			nums[one] = 1
			two++
			one++
		} else {
			nums[two] = 2
			two++
		}
	}
}

總結:

若一陣列要做排序，在僅由少數元素組成的情況下且知道少數元素的值分別為多少，最快只要一次遍歷就能排序完所有的元素，要想辦法在一邊遍歷取代的同時一邊紀錄各元素在排序後陣列上最後一個值的位置，以0,1,2組成的情況下來說，當在遍歷尚未排序的陣列時，如果出現0除了要將0紀錄的位置向後推，連同1、2也要向後推，出現1除了要將1紀錄的位置向後推，連2也要向後推，而出現2就只有2紀錄的位置向後推就好，因為2後頭沒有其它數字，因此不會影響其它數字的位置，最後在先前2後推的同時將一路上的值轉為2到陣列底，接著是1後推的同時將一路上的值轉為1到最後一個值的位置，再來才是0後推的同時將一路上的值轉為0到最後一個值的位置，如此一來三個變數所紀錄0,1,2的位置在分別到達最後一個值位置的同時也排序完整個陣列了。

分享到