leetcode75. 颜色分类

举报
兔老大 发表于 2021/04/23 01:48:04 2021/04/23
【摘要】 给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 注意: 不能使用代码库中的排序函数来解决这道题。 示例: 输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2] 进阶: 一个直观的解决方案是使用计数排...

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

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

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

示例:

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶:

一个直观的解决方案是使用计数排序的两趟扫描算法。
首先,迭代计算出0、1 和 2 元素的个数,然后按照0、1、2的排序,重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗?

思路:改进排序,分三区,小于等于大于


      class Solution {
       /*
       荷兰三色旗问题解
       */
       public void sortColors(int[] nums) {
      // 对于所有 idx < i : nums[idx < i] = 0
      // j是当前考虑元素的下标
      int p0 = 0, curr = 0;
      // 对于所有 idx > k : nums[idx > k] = 2
      int p2 = nums.length - 1;
      int tmp;
      while (curr <= p2) {
      if (nums[curr] == 0) {
      // 交换第 p0个和第curr个元素
      // i++,j++
       tmp = nums[p0];
       nums[p0++] = nums[curr];
       nums[curr++] = tmp;
       }
      else if (nums[curr] == 2) {
      // 交换第k个和第curr个元素
      // p2--
       tmp = nums[curr];
       nums[curr] = nums[p2];
       nums[p2--] = tmp;
       }
      else curr++;
       }
        }
      }
  
 

 

文章来源: fantianzuo.blog.csdn.net,作者:兔老大RabbitMQ,版权归原作者所有,如需转载,请联系作者。

原文链接:fantianzuo.blog.csdn.net/article/details/104080108

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。