前端算法专栏-数组-75.颜色分类

简介: 前端算法专栏-数组-75.颜色分类

介绍

Hi 大家好。我是程序员库里,今天新开一个前端算法专栏。

接下来会分类给大家分享常考算法题目。

很多朋友也是看着这套系列算法拿到很多offer!所以也是想分享给更多朋友,帮助到有需要的朋友。

请在此添加图片描述

分类

数组-三路快排

题目

75. 颜色分类

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

我们使用整数 012 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1:

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

示例 2:

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

解释

1.定义一个变量zero,初始值为-1,zero变量用来表示0...zero区间全部放0

2.定义一个变量two,初始值为数组的长度,two变量用来表示two...n-1区间全部放2

3.zero+1...n-1区间全部放1,这样数组中就变成了0....1....2

4.开始遍历数组,条件是当i小于数组长度的时候

5.如果遍历的当前元素是1,只把i向右移动一位,即i++。因为 1是在数组的中间,所以不做其他操作。

6.如果遍历的当前元素是2,先将变量two向左移动一位,腾出一个位置,也就是two--。然后将当前的元素2和two所在的位置交换一下位置,此时这个2就移动到了右边,这个时候不能将 i 向右移动一位,需要继续判断 当前这个元素是否为0

7.如果遍历的当前元素是0,先将zero向右移动一位,腾出一个位置,也就是zero++。然后将当前的元素0和zero所在的位置交换一下位置,此时这个0就移动到了左边。然后继续遍历,即i++。

8.遍历完一遍后,所有0就到了左边,所有2就到了右边,所有1就到了中间。即完成了数组排序。

代码

/**

* @param {number[]} nums

* @return {void} Do not return anything, modify nums in-place instead.

*/

var sortColors = function(nums) {
   
   

    let zero = -1;// [0...zero] 为0,弄成无效区间

    let two = nums.length;// [two...n-1] 为2,弄成无效区间

    for(let i =0;i<two;){
   
   

        if(nums[i] === 1){
   
   
            i++
        }else if(nums[i] === 2){
   
   
            two--
            [nums[i],nums[two]] = [nums[two],nums[i]]
        }else if(nums[i] === 0){
   
   
            zero++
            [nums[i],nums[zero]] = [nums[zero],nums[i]]
            i++
        }
    }
    return nums;
};
相关文章
|
6天前
|
人工智能 移动开发 算法
【动态规划】【C++算法】LeetCoce996正方形数组的数目
【动态规划】【C++算法】LeetCoce996正方形数组的数目
|
6天前
|
算法 测试技术 C++
【动态规划】【滑动窗口】【C++算法】 629K 个逆序对数组
【动态规划】【滑动窗口】【C++算法】 629K 个逆序对数组
|
27天前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-49 算法训练 寻找数组中最大值
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-49 算法训练 寻找数组中最大值
28 0
|
3天前
|
存储 算法
【数据结构与算法】3、虚拟头节点、动态数组的缩容、动态数组和单链表的复杂度、数组的随机访问
【数据结构与算法】3、虚拟头节点、动态数组的缩容、动态数组和单链表的复杂度、数组的随机访问
10 0
|
5天前
|
机器学习/深度学习 算法 搜索推荐
【实操】数据扩增:Retinex算法用于图像颜色恢复和对比度增强
【实操】数据扩增:Retinex算法用于图像颜色恢复和对比度增强
23 0
【实操】数据扩增:Retinex算法用于图像颜色恢复和对比度增强
|
6天前
|
算法 测试技术 C++
【动态规划】【数学】【C++算法】805 数组的均值分割
【动态规划】【数学】【C++算法】805 数组的均值分割
|
6天前
|
机器学习/深度学习 自然语言处理 算法
如何利用机器学习算法提高分类准确率
【2月更文挑战第7天】机器学习在现代科技中扮演着重要的角色。分类是其中一种基本的机器学习任务,而分类准确率是衡量分类模型好坏的重要指标。本文将介绍如何利用机器学习算法来提高分类准确率。
6 0
|
6天前
|
算法 测试技术 C++
【KMP】【二分查找】【C++算法】100207. 找出数组中的美丽下标 II
【KMP】【二分查找】【C++算法】100207. 找出数组中的美丽下标 II
|
11天前
|
算法 C语言
C语言数组实例(冒泡算法、猜数字)
C语言数组实例(冒泡算法、猜数字)
9 0
|
15天前
|
算法 测试技术 C语言
leecode算法题之数组
leecode算法题之数组

相关产品