LeetCode刷题---75. 颜色分类(双指针,循环不变量)

简介: LeetCode刷题---75. 颜色分类(双指针,循环不变量)



一、编程题:75. 颜色分类(双指针,循环不变量)

1.题目描述

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

必须在不使用库的sort函数的情况下解决这个问题。 LeetCode题目链接。

2.示例1:

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

输出:[0,0,1,1,2,2]

3.示例2:

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

输出:[0,1,2]。

4.提示:

  • n == nums.length
  • 1 <= n <= 300
  • nums[i] 为 0、1 或 2

5.进阶:

  • 你可以不使用代码库中的排序函数来解决这道题吗?
  • 你能想出一个仅使用常数空间的一趟扫描算法吗

二、解题思路

1.思路

解决方法1(个人想法):

  • Step1.创建三个变量用于存储0,1,2出现的个数;
  • Step2.用for循环遍历数组,计算出0,1,2出现的个数;
  • Step3.再用for循环根据0,1,2出现的个数对数组进行重写即可;

解决方法2(双指针,循环不变量):官方视频讲解

  • Step1.定义循环不变量
            all in [0, left) == 0
            all in [left, i) == 1
            all in (right, len - 1] == 2
  • Step2.创建两个指针left,right,其中left=0,right=nums.length-1,left指针用于指向最左边的位置,rigtht指针指向最右边的位置;
  • Step3.当nums[i] == 0时,则与最右边的位置left进行交换,交换之后则left要自加1,并且i自加1(这里用for循环进行遍历时,i不用考虑自加);
  • Step4.当nums[i] == 2时,则与最左边的位置right进行交换,交换之后right要自减1,并保持i不变(这里用for循环时,i要自减1);
  • Step5. 用for实现该双指针时,不需要考虑Step5。 当nums[i] == 1时,不做处理,让循环i自加1即可;

三、代码实现

。每个代码块都写了注释,方便理解,代码还可以改进;

代码如下(示例):

解法一:

class Solution {
    public void sortColors(int[] nums) {
        //第一种方法(分组)
        int zero = 0, one = 0, two = 0;
        for(int right = 0; right < nums.length; right++){
            switch(nums[right]){
                case 0: zero++;break;
                case 1: one++;break;
                case 2: two++;break;
            }
        }
        // System.out.println("zero="+zero+" one="+one+" two="+two);
        for(int right = 0; right < nums.length; right++){
            if(zero > 0){
                nums[right] = 0; zero--;
            }else if(one > 0){
                nums[right] = 1; one--;
            }else if(two > 0){
                nums[right] = 2; two--;
            }
        }
    }
}

解法二:

  • for循环实现
class Solution {
    public void sortColors(int[] nums) {
        //第二种方法(双指针)
        // 循环不变量
        // all in [0, p0) == 0 红
        // all in [p0, i) == 1 白
        // all in (p2, len - 1] == 2 蓝
        // 把红色和蓝色放在两边,中间自然就是白色
        int left = 0, right = nums.length - 1;
        //for循环实现
        for(int i = 0; i < right+1; i++){
            switch(nums[i]){
                case 0:
                    swap(nums, left++, i);
                    break;
                case 2:
                    //当值为2时,则进行交换,并把right指针自减1并保持i不变
                    swap(nums, i--, right--);
                    break;
            }
        }
    }
    public void swap(int[] nums, int left, int right){
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}
  • while循环实现
class Solution {
    public void sortColors(int[] nums) {
        //第二种方法(双指针)
        // 循环不变量
        // all in [0, p0) == 0 红
        // all in [p0, i) == 1 白
        // all in (p2, len - 1] == 2 蓝
        // 把红色和蓝色放在两边,中间自然就是白色
        int left = 0, right = nums.length - 1;
        //while循环实现
        int i = 0;
        while(i <= right){
            switch(nums[i]){
                case 0:
                    swap(nums, left++, i++);
                    break;
                case 1:
                    i++;
                    break;
                case 2:
                    swap(nums, i, right--);
                    break;
            }
        }
    }
    public void swap(int[] nums, int left, int right){
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

提交结果:


总结

以上就是今天要讲的内容,一开始做题的时候,首先想到就是用for循环遍历计数,然后再用for循环重写原数组,后面看了官方视频讲解之后,接触到一个新概念:循环不变量,根据循环不变量以及双指针思想在对该题进行理解,对双指针思想的印象很深刻,所以就赶紧记录一下这个方法,开阔一下思路。

感谢观看,如果有帮助到你,请给题解点个赞和收藏,让更多的人看到。🌹 🌹 🌹

也欢迎你,关注我。👍 👍 👍

原创不易,还希望各位大佬支持一下,你们的点赞、收藏和留言对我真的很重要!!!💕 💕 💕 最后,本文仍有许多不足之处,欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正!


相关文章
|
5天前
|
存储 C语言
指针变量
指针变量
14 2
|
8天前
|
存储 C++
C++程序指针变量:深入理解与实践
C++程序指针变量:深入理解与实践
13 1
|
23小时前
|
算法
"刷题记录:哈希表+双指针 | leetcode-2465. 不同的平均值数目 "
该文段是一篇关于编程题目的解答,主要讨论如何找到数组中所有不同平均值的个数。作者首先使用排序和哈希集来解决,将数组转为列表排序后,通过双指针计算平均值并存入哈希集以去重。然后,作者发现可以优化方案,通过双指针在排序后的数组中直接计算两数之和,用哈希集记录不重复的和,从而避免实际计算平均值,提高了算法效率。最终代码展示了这两种方法。
8 0
|
1天前
|
存储 算法 索引
【力扣刷题】只出现一次的数字、多数元素、环形链表 II、两数相加
【力扣刷题】只出现一次的数字、多数元素、环形链表 II、两数相加
10 1
|
1天前
【力扣刷题】二叉树的中序遍历、二叉树的最大深度、翻转二叉树、对称二叉树
【力扣刷题】二叉树的中序遍历、二叉树的最大深度、翻转二叉树、对称二叉树
6 0
|
1天前
|
索引
【力扣刷题】回文链表、环形链表、合并两个有序链表
【力扣刷题】回文链表、环形链表、合并两个有序链表
7 0
|
4天前
|
算法 索引
力扣刷题【第一期】
这是一个关于算法的总结,包含7个不同的问题。1)爬楼梯问题,使用动态规划,通过迭代找到到达n阶楼梯的不同方法数。2)两数之和,通过双重循环找出数组中和为目标值的两个数的索引。3)移动零,使用双指针将数组中的0移到末尾。4)合并有序链表,创建新链表按升序合并两个链表。5)删除链表重复值,遍历链表删除重复元素。6)环形链表检测,使用快慢指针判断链表是否有环。7)相交链表,计算链表长度找
8 1
|
4天前
|
存储 Java
JAVA数据结构刷题 -- 力扣二叉树
JAVA数据结构刷题 -- 力扣二叉树
10 0
|
5天前
|
C语言
用指针函数变量调用函数
用指针函数变量调用函数
7 2
|
5天前
|
存储
指针用法及分类
指针用法及分类