今天面试就先到这里吧,回去等通知吧!

通知:吴师兄学算法训练营第十期开启报名,预计 12 月 20 开营,解锁 400 题。

一、题目描述

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

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

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

示例 1:

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

示例 2:

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

提示:

  • n == nums.length
  • 1 <= n <= 300
  • nums[i]012

进阶:

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

二、题目解析

这道题目有很多种解法。

但千万别做个“大聪明”,使用 sort 排序函数:

Arrays.sort(nums);
今天面试就先到这里吧,回去等通知吧!

一行代码也通过了,但面试结果就是:今天面试就先到这里吧,回去等通知吧!

今天面试就先到这里吧,回去等通知吧!

(图片来源于 LeetCode 75 号问题题解评论区

因为题目有几个限制:

  • 1、原地操作
  • 2、不能使用代码库中的排序函数
  • 3、常数级别的空间复杂度
  • 4、扫描一遍

使用上面的 sort 函数就是和面试官较劲了。。。

这道题目是非常经典的「荷兰国旗问题」,由计算机科学家 Edsger W. Dijkstra 首先提出,掌握这道题目对于后续学习快速排序三指针等知识点非常有帮助。

直接来说解法。

设置 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 先不移动

三、参考代码

// LeetCode 100 题精讲:https://mp.weixin.qq.com/s/yznC53g46phq3qF7V4-obA
// 作者:程序员吴师兄
// 颜色分类(LeetCode 75):https://leetcode.cn/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,index,right);

                // 由于原先 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;
    }
}

提交通过。

今天面试就先到这里吧,回去等通知吧!


玩转 LeetCode 高频 100 题系列正在更新

数组篇

1、LeetCode 283:移动零

系列介绍:LeetCode 刷多少题能进大厂面试?