首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >只想刷 easy 题......

只想刷 easy 题......

作者头像
五分钟学算法
发布2022-05-27 16:03:59
2170
发布2022-05-27 16:03:59
举报
文章被收录于专栏:五分钟学算法五分钟学算法

大家好,我是吴师兄。

今天分享的题目是 LeetCode 第 75 号问题:颜色分类

这道题目可以很好的考察你对于快速排序的理解程度,所以考察的频率还挺高的。

同时,它也是一道中等题,做不出难题的情况下,做一做中等题压压惊吧。

还做不出来,那就刷刷 easy 题吧。

题目描述

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

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

题目解析

设置 3 个索引,left 指向数组的开始位置,right 指向数组的结束位置,index 指向数组的开始位置。

我们让 index 从头开始向后移动,在移动的过程中,它指向的元素会出现三种情况:

  • 如果 index位置上的元素值为 0,则说明是红色,要放在最前面去,此时最前面的那个元素被 left 指着,所以让 index 指向的元素和 left 指向位置上的元素进行交换,交换完毕之后,说明 0 已经在它应该在的位置,即在整个数组的左区域,所以 left 可以向后移动,index 也向后移动
  • 如果若 index 位置上的元素值为 1,则说明是白色,就应该放在中间,不用管它,继续移动 index
  • 如果 index 位置上的元素值为 2,则说明是蓝色,要放在最后面,此时最后面的那个元素被 right 指着,所以让 index 指向的元素和 right 指向位置上的元素进行交换,交换完毕之后,说明 2 已经在它改在的位置,即在整个数组的右区域,right 向前移动,但由于原先 right 指向的元素可能为 0、1、2 这三种的任何一种,到了 index 后,还需要继续观察一轮,所以 index 先不移动

参考代码

// 登录 AlgoMooc 官网获取更多算法图解
//  https://www.algomooc.com/567.html
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 颜色分类( LeetCode 75 ):https://leetcode-cn.com/problems/sort-colors/
class Solution {
    public void sortColors(int[] nums) {
        
        // left  指向数组的开始的位置,它指向的位置左侧都是 0
        int left = 0;

        // right  指向数组的结束的位置,它指向的位置右侧都是 2
        int right = nums.length - 1;

        // index 指向数组的开始位置
        int index = 0;

        // index 向后移动,当它越过 right 时跳出循环,不需要再判断了
        // 因为此时说明 index 右侧的都已经是 2
        while( index <= right ){

            // 获取当前的元素值
            int cur = nums[index];
            
            // 如果 index 位置上的元素值为 0
            if(cur == 0){
              // 说明是红色,要放在最前面去
              // 最前面的那个元素被 left 指着,所以让 index 指向的元素和 left 指向位置上的元素进行交换
              swap(nums,left,index);

              // index 可以向后移动
              index++;

              // left 可以向后移动,它的左侧区域都是 0
              left++;

              // 如果 index 位置上的元素值为 1
            }else if(cur == 1){
                // 说明是白色,就应该放在中间,不用管它,继续移动 index
                index++;

                // 如果 index 位置上的元素值为 2
            }else if(cur == 2){

                // 说明是蓝色,要放在最后面
                // 所以让 index 指向的元素和 right 指向位置上的元素进行交换
                swap(nums,right,index);

                // 由于原先 right 指向的元素可能为 0、1、2 这三种的任何一种
                // 交换到了 index 后,还需要继续观察一轮,所以 index 先不移动
                right--;
            }
        }

    }

    // 通过中间变量,交换两个元素的值
    // nums[i] 的值变为了 nums[j] 的值 
    // nums[j] 的值变为了 nums[i] 的值 
    private void swap(int[] nums, int i ,int j){
        // 使用临时变量 temp,保存 nums[i] 的值
        int temp = nums[i];
        
        // nums[i] 的值修改为 nums[j] 的值
        nums[i] = nums[j];

        // nums[i] 的值修改为 temp 的值
        nums[j] = temp;
    }
}
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2022-04-21,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 五分钟学算法 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
  • 题目解析
  • 参考代码
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档