75. Sort Colors

发表于 | 分类于

每日一题 2019 - 04 - 10

题目：

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library’s sort function for this problem.

Example:

1
2
Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Follow up:

  • A rather straight forward solution is a two-pass algorithm using counting sort.
    First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.
  • Could you come up with a one-pass algorithm using only constant space?

解法：

这个题需要对给定序列进行排序，这个序列里面只有三类数字，分别是0 、1、2，要求是每个数字都聚在一起，就像 example 给出的例子，直观的解题思路，一个sort函数就可以解决问题，但是这个题让我们尝试使用使用一趟遍历就解决问题，所以就引进了一个新的算法，也即Dutch national flag problem ；

这个算法的思路简单可解释如下：

  • 设置三指针 i、j、 n，
    • i 代表最小元素往后递推的当前所处位置
    • j 代表当前遍历的位置
    • n 代表最大元素当前往前递推所处的位置
  • 设置 mid 为待排三元素的中间值
  • 随后开始遍历：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
while(j <= n)
{
    // 如果当前元素比中间值小，那么证明当前元素应该往前排
    if( nums[j] < mid )
    {
        //将当前元素排到 i 位置
        swap(nums[i],nums[j]);
        i ++;
        j ++;
    }  
    // 如果当前元素比中间值大，那么证明当前元素应该往后排
    else if( nums[j] > mid)
    {
        swap(nums[j],nums[n]);
        n -- ;
    }
    // 如果当前元素为中间值，继续往后遍历
    else
    {
        j ++ ;
    }
}

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int mid = 1 ;
        int n = nums.size() - 1 ;
        int i = 0 ; 
        int j = 0 ;
        while(j <= n)
        {
            if( nums[j] < mid )
            {
                swap(nums[i],nums[j]);
                i ++;
                j ++;
            }  
            else if( nums[j] > mid)
            {
                swap(nums[j],nums[n]);
                n -- ;
            }
            else
            {
                j ++ ;
            }
        }
    }
};
0%
undefined