curTain

  1. 颜色分类

75. 颜色分类

给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:
不能使用代码库中的排序函数来解决这道题。

示例:

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

进阶:

一个直观的解决方案是使用计数排序的两趟扫描算法。
首先,迭代计算出0、1 和 2 元素的个数,然后按照0、1、2的排序,重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗?

解法一:冒泡排序

1
2
3
4
5
6
7
8
9
10
var sortColors = function(nums) {
for( let i = 0; i < nums.length - 1; i ++ ){
for( let j = i + 1; j < nums.length; j ++ ){
if( nums[i] > nums[j] ){
[ nums[i], nums[j] ] = [ nums[j], nums[i] ]
}
}
}
return nums
}

解法二:单指针

解题思路:使用单指针,依次排 01,需要进行 n-1 次循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var sortColors = function(nums) {
let index = 0
for( let i = 0; i < nums.length; i ++ ){
if( nums[i] === 0 ){
[ nums[i], nums[index] ] = [ nums[index], nums[i] ]
index ++
}
}
for( let i = index; i < nums.length; i ++ ){
if( nums[i] === 1 ){
[ nums[i], nums[index] ] = [ nums[index], nums[i] ]
index ++
}
}
return nums
}

解法二:双指针

解题思路:

  1. 使用一个指针记录 0 的下标
  2. 使用一个指针记录 2 的下标
  3. 向中间逼近,中间的元素就是 1

该方法比较适合只有三个元素排序的数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var sortColors = function(nums) {
let sIndex = 0
let eIndex = nums.length - 1
let i = 0
while( i <= eIndex ){
if( nums[i] === 0 ){
[ nums[i], nums[sIndex] ] = [ nums[sIndex], nums[i] ]
sIndex ++
}
if( nums[i] === 2 ){
[ nums[i], nums[eIndex] ] = [ nums[eIndex], nums[i] ]
eIndex --
// 位置回退,因为不知道交换后的元素的值,故需要重新判断一次
i--
}
i++
}
return nums
};

 评论