给定一个包含红色、白色和蓝色，一共 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]
解法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68object SortColors {
def main(args: Array[String]): Unit = {
val arr = Array(0, 2, 2, 2, 0, 2, 1, 1)
sortColors(arr)
println(java.util.Arrays.toString(arr))
val arr1 = Array(2, 1, 2, 0, 1, 1, 1, 1, 1)
sortColors(arr1)
println(java.util.Arrays.toString(arr1))
val arr2 = Array(2)
sortColors(arr2)
println(java.util.Arrays.toString(arr2))
val arr3 = Array(0, 0)
sortColors(arr3)
println(java.util.Arrays.toString(arr3))
val arr4 = Array(2, 0, 1)
sortColors(arr4)
println(java.util.Arrays.toString(arr4))
val arr5 = Array(2, 0, 2, 1, 1, 0)
sortColors(arr5)
println(java.util.Arrays.toString(arr5))
}
/**
* 双指针，时间复杂度O(n)
*/
def sortColors(nums: Array[Int]): Unit = {
if (nums.length <= 1) return
var i = 0
var s = 0
var e = nums.length - 1
while (s < nums.length && nums(s) == 0) {
s += 1
}
i = s
while (i <= e) {
nums(i) match {
case 0 =>
swap(nums, i, s)
while (s <= e && nums(s) == 0) {
s += 1
}
i = s
case 1 =>
swap(nums, i, s)
i += 1
case 2 =>
swap(nums, i, e)
while (e >= s && nums(e) == 2) {
e -= 1
}
}
}
}
def swap(nums: Array[Int], i: Int, j: Int): Unit = {
val t = nums(i)
nums(i) = nums(j)
nums(j) = t
}
}