LeetCode 75. 颜色分类
题目描述
🔥 75. 颜色分类
思路分析
思路分析：
- 使用三个指针：
left、cur和right，分别指向已经处理好的 0 序列的下一个位置、当前待处理元素的位置以及已经处理好的 2 序列的前一个位置。- 遍历数组，根据当前元素的值进行交换操作：
- 如果
nums[cur]等于 0，将其与nums[left]交换，并将left和cur同时右移。- 如果
nums[cur]等于 2，将其与nums[right]交换，并将right左移。由于交换后的nums[cur]可能是 1 或 0，所以不将cur右移，继续处理这个位置的元素。- 如果
nums[cur]等于 1，不需要交换，将cur右移。- 当
cur指针超过right指针时，排序完成。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func sortColors(nums []int) {
left, right := 0, len(nums)-1
cur := 0
for cur <= right {
if nums[cur] == 0 {
nums[cur], nums[left] = nums[left], nums[cur]
left++
cur++
} else if nums[cur] == 2 {
nums[cur], nums[right] = nums[right], nums[cur]
right--
} else {
cur++
}
}
}
1
write your code here
拓展题目
题目描述：给定一个包含正整数的数组，要求按照以下规则对数组进行排序，同时保持常数空间复杂度：
- 将数组中对 3 取模等于 0 的元素移动到数组的左边。
- 将数组中对 3 取模等于 2 的元素移动到数组的右边。
- 对 3 取模等于 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
func sortColors(nums []int) {
left, right := 0, len(nums)-1
i := 0
for i <= right {
switch nums[i] % 3 {
case 0:
nums[left], nums[i] = nums[i], nums[left]
left++
i++
case 1:
i++
case 2:
nums[right], nums[i] = nums[i], nums[right]
right--
}
}
}
func main() {
nums := []int{2, 1, 0, 2, 0, 1, 2, 1, 0}
sortColors(nums)
fmt.Println(nums) // 输出结果应为 [0 0 0 1 1 1 2 2 2]
nums = []int{7, 15, 11, 9, 8, 10, 13, 5, 6, 4}
sortColors(nums)
fmt.Println(nums) // 输出结果应为 [15 9 6 7 4 10 13 5 8 11]
}
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！