LintCode 148. 颜色分类 JavaScript算法

时间:2020-9-12 作者:admin

描述

给定一个包含红,白,蓝且长度为 n 的数组,将数组元素进行分类使相同颜色的元素相邻,并按照红、白、蓝的顺序进行排序。

我们可以使用整数 0,1 和 2 分别代表红,白,蓝。

说明

不能使用代码库中的排序函数来解决这个问题。
排序需要在原数组中进行。

样例

- 样例 1:

输入 : [1, 0, 1, 2]
输出 : [0, 1, 1, 2]
解释 : 原地排序。

挑战

一个相当直接的解决方案是使用计数排序扫描2遍的算法。

首先,迭代数组计算 0,1,2 出现的次数,然后依次用 0,1,2 出现的次数去覆盖数组。

你否能想出一个仅使用常数级额外空间复杂度且只扫描遍历一遍数组的算法?

解析

sortColors=function (nums) {
    return nums.sort()
}

运行结果

LintCode 148. 颜色分类 JavaScript算法

LintCode 148. 颜色分类 JavaScript算法

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。