颜色分类( LeetCode 75 )

本文内容为算法训练营一期内容,仅限训练营学员观看

一、题目描述

给定一个包含红色、白色和蓝色,一共 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 先不移动

三、参考代码

1、Java 代码

// 登录 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;
    }
}

2、C++ 代码

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

        // right  指向数组的结束的位置,它指向的位置右侧都是 2
        int right = nums.size() - 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] 的值 
     void swap(vector<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;
     }
};

3、Python 代码

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

        # right  指向数组的结束的位置,它指向的位置右侧都是 2
        right = len(nums) - 1

        # index 指向数组的开始位置
        index = 0

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

            # 获取当前的元素值
            cur = nums[index]

            # 如果 index 位置上的元素值为 0
            if cur == 0 :
              # 说明是红色,要放在最前面去
              # 最前面的那个元素被 left 指着,所以让 index 指向的元素和 left 指向位置上的元素进行交换

              self.swap(nums,left,index)

              # index 可以向后移动
              index += 1

              # left 可以向后移动,它的左侧区域都是 0
              left += 1

              # 如果 index 位置上的元素值为 1
            elif cur == 1 :
                # 说明是白色,就应该放在中间,不用管它,继续移动 index
                index += 1

                # 如果 index 位置上的元素值为 2
            elif cur == 2 : 

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

                # 由于原先 right 指向的元素可能为 0、1、2 这三种的任何一种
                # 交换到了 index 后,还需要继续观察一轮,所以 index 先不移动
                right -= 1
    # 通过中间变量,交换两个元素的值
    # nums[i] 的值变为了 nums[j] 的值 
    # nums[j] 的值变为了 nums[i] 的值 
    def swap(self,nums: List[int], i : int ,j : int):
        # 使用临时变量 temp,保存 nums[i] 的值
        temp = nums[i]

        # nums[i] 的值修改为 nums[j] 的值
        nums[i] = nums[j]

        # nums[i] 的值修改为 temp 的值
        nums[j] = temp

四、动画理解(没有声音)

隐藏内容
  • 普通用户购买价格:不可购买
  • 会员用户购买价格:999积分
  • 永久会员用户购买价格:免费推荐

发表评论

邮箱地址不会被公开。 必填项已用*标注