力扣题75颜色分类

wuchangjian2021-11-15 10:53:03编程学习

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

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

示例 1:

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

示例 2:

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

示例 3:

输入:nums = [0]
输出:[0]

示例 4:

输入:nums = [1]
输出:[1]

1.单指针法:需要遍历2次,第一次遍历将0放在前面,第二次遍历将1排在0后面。

class Solution {
    public void sortColors(int[] nums) {
        int index = 0;
        //第一次遍历将0放在最前面
        for(int i = 0;i < nums.length;i++){
            if(nums[i] == 0){
                int temp = nums[index];
                nums[index] = nums[i];
                nums[i] = temp;
                index++;
            }
        }
        //第二次遍历将1排在0的后面
        for(int i = index;i < nums.length;i++){
            if(nums[i] == 1){
                int temp = nums[index];
                nums[index] = nums[i];
                nums[i] = temp;
                index++;
            }
        }
    }
}

2.双指针法:只用遍历一次。

class Solution {
    public void sortColors(int[] nums) {
        int index1 = 0;
        int index2 = nums.length - 1;
        //只遍历一次数组
        for(int i = 0;i <= index2;i++){
            //如果遇到的是2,交换到末尾,但是因为可能交换回来的也是2,就要一直循环,直到交换回来的数字不是2
            while(i <= index2 && nums[i] == 2){
                int temp = nums[i];
                nums[i] = nums[index2];
                nums[index2] = temp;
                index2--;//末尾增加一个2,末尾指针向前移
            }
            //如果此时遍历到的是0,就放到开头
            if(nums[i] == 0){
                int temp = nums[index1];
                nums[index1] = nums[i];
                nums[i] = temp;
                index1++;//开头增加1个0,开头指针向后移
            }
        }
    }
}

3.双指针法的继续优化:遍历一次数组,遇到0就放到前面,遇到2就放到后面,注意,如果交换后该遍历位置上的值不是1,就需要后退指针一步,在后面的++中使该指针保持在原地再判断一次非1数,因为0和2都是需要移动的。

class Solution {
    public void sortColors(int[] nums) {
        int index1 = 0;
        int index2 = nums.length - 1;

        for(int i = 0;i <= index2;i++){
            if(nums[i] == 0){//把0交换到最前面
                int temp = nums[i];
                nums[i] = nums[index1];
                nums[index1] = temp;
                index1++;
            }

            if(nums[i] == 2){//把2交换到最后面
                int temp = nums[i];
                nums[i] = nums[index2];
                nums[index2] = temp;
                index2--;
                if(nums[i] != 1){//这一步判断移动回来的是不是1很关键
                    i--;
                }
            }
        }
    }
}

题源:力扣

相关文章

ndk-build.cmd‘‘ finished with non-zero exit value 2

具体错误: Execution failed for task '...

粉丝量几何级增长

粉丝量几何级增长

昨天上午9点多的时候我发了一条朋友圈。 这张照片是我拍的,我自己甚是...

jsp代码实例第153课

code153.jsp <%@ page language=&#...

洛谷U187640a++b?及想法拓展

很多人说想念a+b了,那么就给大家写一道a++b吧...

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。