题目

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

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

注意:

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

示例:

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

进阶:

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

解题

解法一: 计数排序, 在该题目中分别统计出 0、1、2 出现的个数, 并将相应个数的 0、1、2 放回数组。

计数排序适用于数组元素非常有限的场景。

输入
[2,0,2,1,1,0]
输出
[0,1,2,1,1,0]
预期结果
[0,0,1,1,2,2]
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var sortColors = function (nums) {
let countObj = {}
for (let i = 0; i < nums.length; i++) {
const key = nums[i]
if (typeof(countObj[`${key}`]) === 'number') {
countObj[`${key}`] = countObj[`${key}`] + 1
} else {
countObj[`${key}`] = 1
}
}
const count0 = countObj[0] || 0
const count1 = countObj[1] || 0
const count2 = countObj[2] || 0
for (let i = 0; i < count0 + count1 + count2; i++) {
if (i < count0) {
nums[i] = 0
} else if (i >=count0 && i < count0 + count1) {
nums[i] = 1
} else if (i >= count1 && i < count0 + count1 + count2) {
nums[i] = 2
}
}
}

解法二: 三路快排

思路: 三路快排的思想是同时排序小于选定值,等于选定值和大于选定值三种情况。在这里我们随机选取一个值 v 作为分界点, 分别排序小于 v,等于 v 和大于 v 的。该题中 v 为 1。

/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var sortColors = function (nums) {
/**
* nums[0, zero] = 0
* nums[two, nums.length - 1] = 2
*/
let [zero, two] = [0, nums.length - 1]
for (let i = 0; i <= two; i++) {
if (nums[i] === 0) {
[nums[i], nums[zero]] = [nums[zero], nums[i]]
zero++
}
if (nums[i] === 2) {
[nums[i], nums[two]] = [nums[two], nums[i]]
i--
two--
}
}
}

该算法的时间复杂度为 O(n), 空间复杂度为 O(1)。

镜像题目

88、215