欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

一首歌的时间看懂荷兰三色旗问题

程序员文章站 2022-03-04 17:55:24
...

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

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

注意:

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

示例:

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

下面看下代码:

/*
荷兰三色旗问题解
*/


class Solution {
  public:

//p0追踪0的最右边界,p2追踪2的最左边界  	
  
void sortColors(vector<int>& nums) {
    // 对于所有 idx < p0 : nums[idx < p0] = 0
    // curr 是当前考虑元素的下标
    int p0 = 0, curr = 0;
	
    // 对于所有 idx > p2 : nums[idx > p2] = 2
    //p2首先指向数组最后一个下标
    int p2 = nums.size() - 1;

    while (curr <= p2) {
      if (nums[curr] == 0) {
        swap(nums[curr++], nums[p0++]);
      } else if (nums[curr] == 2) {
        swap(nums[curr], nums[p2--]);
      }
      else curr++;
    }
  }
};

 该算法用了用3个指针,p0追踪0的最右边界,p2追踪2的最左边界 ,curr表示当前下标。遇到等于0或2的时候就进行交换,并且对p0或p2进行操作,思路很巧妙。

时间复杂度:O(N)

空间复杂度:O(1)

 

参考地址:https://leetcode-cn.com/problems/sort-colors/solution/yan-se-fen-lei-by-leetcode/

 

相关标签: 数据结构与算法