前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >[LeetCode]75.颜色分类——题解(执行用时击败90% ,内存消耗击败 78%)

[LeetCode]75.颜色分类——题解(执行用时击败90% ,内存消耗击败 78%)

作者头像
用户6557940
发布2022-07-24 15:18:53
4220
发布2022-07-24 15:18:53
举报
文章被收录于专栏:Jungle笔记Jungle笔记

01

题目描述

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

注意:不能使用代码库中的排序函数来解决这道题。

示例:

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

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

02

分析

显然,最直观的方法是通过一次遍历统计出0、1、2的个数,再按照0、1、2的顺序重写该数组。但该方法需要两次扫描。那有没有通过一次扫描就完成排列的方法呢?答案是:有!

问题1:思路是什么?

观察题目描述和题目示例的输出,0排在序列最前面,2排在序列最后面,因此,在扫描数组时,我们可以判断当前数字的值:

  • 如果是0,就往数列前部移动;
  • 如果是2,就往数列后部移动。

问题2:如何前移后移

此时抛出另一个问题:往前部移动,移动到哪里呢?往后部移动,又移动到哪里呢?

——设置两个标记flag0和flag2。

开始时我们并不知道最终会有多少个0,但数列最前面一定是0,因此flag0初始值为数列最前面,即0;同样,开始时我们并不知道最终有多少个2,但数列最后面一定是2,所以flag2初始值为数组最后一个元素索引位置。初始化完毕后,接下来开始扫描过程(即更新标记flag0和flag2的过程):

  • 如果当前元素是0,将当前元素与索引为flag0的元素互换位置,flag0++;
  • 如果当前元素是2,将当前元素与索引为flag2的元素互换位置,flag2--。

问题3:如果序列里没有0或者没有2呢?

如果序列里没有0,那么flag0始终指向数组第一个位置;同理,如果序列里没有2,flag2始终为数组最后一个元素索引位置。

问题4:如果当前元素为1,怎么处理?

不处理!为什么不处理呢?就因为有两个标记flag0和flag2的存在,因为两个标记严格限定了0和2的边界,自然而言,两个边界之间的就是1了。

03

代码

代码语言:javascript
复制
void swap(vector<int>& nums, int i, int j){
  int temp = nums[i];
  nums[i] = nums[j];
  nums[j] = temp;
}
 
void sortColors(vector<int>& nums) {
  //初始化标记
  int flag0 = 0;
  int flag2 = nums.size() - 1;
  for (int i = 0; i <= flag2; i++){
    if (nums[i] == 2){
      swap(nums, i, flag2);
      flag2--;
      i--;//之所以要i--,是因为交换到i处的值可能是0
    }
    else if (nums[i] == 0){
      swap(nums, i, flag0);
      flag0++;
    }
  }
}

04

执行结果

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-10-12,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Jungle笔记 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档