首页 > itarticle > 颜色分类

颜色分类

admin 11月 11, 2020 0

来源Leetcode第75题颜色分类

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

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

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

示例:

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

库函数

直接调用库函数Arrays.sort(nums);就完事了

2次遍历

一次遍历先统计3个球的总数，二次遍历重写数组

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
public void (int[] nums) {
    if (nums.length == 0)
        return;
    int nums0 = 0,nums1 = 0,nums2 = 0;
    for(int i = 0 ; i < nums.length ; i ++){
        if(nums[i] == 0)
            nums0++;
        else if(nums[i] == 1)
            nums1++;
        else if(nums[i] == 2)
            nums2++;
    }
    nums1 += nums0;
    nums2 += nums1;
    for(int i = 0 ; i < nums.length ; i++){
        if(i < nums0)
            nums[i] = 0;
        else if(i < nums1)
            nums[i] = 1;
        else
            nums[i] = 2;
    }
}

双指针

用三个指针（p0, p2 和curr）来分别追踪0的最右边界，2的最左边界和当前考虑的元素。
沿着数组移动 curr 指针，若nums[curr] = 0，则将其与 nums[p0]互换；若 nums[curr] = 2 ，则与 nums[p2]互换。

  • 初始化0的最右边界：p0 = 0。在整个算法执行过程中 nums[idx < p0] = 0.
  • 初始化2的最左边界 ：p2 = n - 1。在整个算法执行过程中 nums[idx > p2] = 2.
  • 初始化当前考虑的元素序号 ：curr = 0.
  • While curr <= p2 :
    • 若 nums[curr] = 0 ：交换第 curr个 和 第p0个 元素，并将指针都向右移。
    • 若 nums[curr] = 2 ：交换第 curr个和第 p2个元素，并将 p2指针左移 。
    • 若 nums[curr] = 1 ：将指针curr右移。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
  public void (int[] nums) {
      if (nums.length == 0)
          return;
      int p0 = 0;

      int p2 = nums.length-1;
//2的边界指针
      int cur = 0;
//当前数组指针
      while(cur <= p2){
//3种交换情况
          if(nums[cur] == 0){
              int tmp = nums[p0];
              nums[p0++] = nums[cur];
              nums[cur++] = tmp;
          }else if(nums[cur] == 2){
              int tmp = nums[p2];
              nums[p2--] = nums[cur];
              nums[cur] = tmp;
          }else{
              cur++;
          }
      }
  }

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能