• 【LeetCode-75】 颜色分类


    6.14 颜色分类【75】

    6.14.1 题目描述

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

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

    必须在不使用库的sort函数的情况下解决这个问题。
    在这里插入图片描述

    6.14.2 方法一:单指针

    思路与算法

    在这里插入图片描述

    class Solution {
        public void sortColors(int[] nums) {
            int n = nums.length;
            int ptr = 0;
            for (int i = 0; i < n; ++i) {
                if (nums[i] == 0) {
                    int temp = nums[i];
                    nums[i] = nums[ptr];
                    nums[ptr] = temp;
                    ++ptr;
                }
            }
            for (int i = ptr; i < n; ++i) {
                if (nums[i] == 1) {
                    int temp = nums[i];
                    nums[i] = nums[ptr];
                    nums[ptr] = temp;
                    ++ptr;
                }
            }
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    复杂度分析

    • 时间复杂度:O(n),其中 n 是数组 nums 的长度。
    • 空间复杂度:O(1)。

    6.14.3 方法二:双指针

    思路与算法
    在这里插入图片描述

    class Solution {
        public void sortColors(int[] nums) {
            int n = nums.length;
            int p0 = 0, p1 = 0;
            for (int i = 0; i < n; ++i) {
                if (nums[i] == 1) {
                    int temp = nums[i];
                    nums[i] = nums[p1];
                    nums[p1] = temp;
                    ++p1;
                } else if (nums[i] == 0) {
                    int temp = nums[i];
                    nums[i] = nums[p0];
                    nums[p0] = temp;
                    if (p0 < p1) {
                        temp = nums[i];
                        nums[i] = nums[p1];
                        nums[p1] = temp;
                    }
                    ++p0;
                    ++p1;
                }
            }
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    复杂度分析

    • 时间复杂度:O(n),其中 n 是数组 nums 的长度。
    • 空间复杂度:O(1)。

    6.14.4 方法三:双指针

    思路与算法
    在这里插入图片描述

    class Solution {
        public void sortColors(int[] nums) {
            int n = nums.length;
            int p0 = 0, p2 = n - 1;
            for (int i = 0; i <= p2; ++i) {
                while (i <= p2 && nums[i] == 2) {
                    int temp = nums[i];
                    nums[i] = nums[p2];
                    nums[p2] = temp;
                    --p2;
                }
                if (nums[i] == 0) {
                    int temp = nums[i];
                    nums[i] = nums[p0];
                    nums[p0] = temp;
                    ++p0;
                }
            }
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    复杂度分析

    • 时间复杂度:O(n),其中 n 是数组 nums 的长度。
    • 空间复杂度:O(1)。

    6.14.5 my answer—统计0 1 2的个数

    class Solution {
        public void sortColors(int[] nums) {
            List<Integer> list0 = new ArrayList<>();
            List<Integer> list1 = new ArrayList<>();
            List<Integer> list2 = new ArrayList<>();
            for (int num : nums) {
                if(num==0)list0.add(num);
                if(num==1)list1.add(num);
                if(num==2)list2.add(num);
            }
            for (int i = 0; i < nums.length; i++) {
                if (i<list0.size())nums[i]=0;
                else if(i<list0.size()+list1.size())nums[i]=1;
                else nums[i]=2;
            }
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
  • 相关阅读:
    飞项聊职场:剖析产品经理和项目经理关键技能
    堆排序代码模板
    【无标题】element select下拉框下拉选项位置不对,显示到旁边,不显示到下拉框底部
    CSP认证202305-2矩阵运算(c++)
    小张的秋招面经(持续更新版)
    STM32 invalid UTF-8 in comment 警告解决办法
    通天星CMSV6车载监控平台CompanyList信息泄露漏洞
    企业ERP和泛微OA集成场景分析
    PostgreSQL 查询语句大全
    记账心得分享
  • 原文地址:https://blog.csdn.net/xiaoguanglin/article/details/126224857