5

今天面试就先到这里吧，回去等通知吧！

 2 years ago
source link: https://www.cxyxiaowu.com/21814.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

一、题目描述

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

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

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

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
输入：nums = [2,0,1]
输出：[0,1,2]
  • n == nums.length
  • 1 <= n <= 300
  • nums[i] 为 0、1 或 2
  • 你可以不使用代码库中的排序函数来解决这道题吗？
  • 你能想出一个仅使用常数空间的一趟扫描算法吗？

二、题目解析

这道题目有很多种解法。

但千万别做个“大聪明”，使用 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;
    }
}

提交通过。

今天面试就先到这里吧，回去等通知吧！

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK