leetcode - 75. 颜色分类(java)-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode - 75. 颜色分类(java)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

leetcode - 75. 颜色分类

难度 - 中等
原题链接 - 颜色分类

题目描述

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 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] 为 0、1 或 2

leetcode - 75. 颜色分类(java),java,算法,数据结构,leetcode,java,算法,数据结构

双指针

该题为经典的荷兰国旗问题，由于题目本质是要我们将数分成三段。
具体步骤：
我们用L 和 R 卡住左边和边，左边放0，右边放1，中间位置放1，
遍历到0时放在左边，指针向右移动，继续比较
碰到1时，什么都不用做，继续向右比较，
碰到2时，放到右边。这样下来就分成了三层。
一次遍历就完成了。

代码演示

/** 
*分层
*/
public void sortColors(int[] nums) {
		//左边界，最开始左边没数据，用-1位置代替
      int l = -1;
      //右边没数据，初始化为数组长度
      int r = nums.length;
      //指针位置，比较
      int index = 0;
      while(index < r){
          if(nums[index] == 0){
              swap(nums,++l,index++);
          }else if(nums[index] == 1){
              index++;
          }else{
              swap(nums,index,--r);
          }
      }

    }
    //交换的方法
    void swap(int[] nums, int i, int j) {
      int temp = nums[i];
      nums[i] = nums[j];
      nums[j] = temp;
    }