Sort Colors

week1

题目链接

题目描述

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:

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?

解题思路

这道题主要是对已知数的排序，数组中的每一个数的范围都已确定，因此用以往的排序如快排，归并排序并不合适，要做到一次遍历完成并使用常空间，所以我选择使用插排来完成。

先使用普通的插排发现时间会很慢，而在这个过程中发现一般的插排都是逐个比较的，而这道题目的特殊点在于数的种类较少只有3个，而且是已知的，那么我们可以记录下每个数应插到的位置，就节省了比较的过程。

记录下0，1，2的可插入点的前一位，比如插入1后，1可插点向后移，而2因为只能在1后，所以也向后移，而0不受1影响，插入点不变。最重要的一点是当插入0/1时，会替换掉原本的数，因为后面的数向后移动，可以当作(1，2)/2也插入到数组中（后移替换掉原本的数）。

代码

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
28
29
30
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int red = -1, white = -1, blue = -1;
        for(int i = 0; i < nums.size(); i ++)
        {
            if(nums[i] == 0)
            {
                red++;
                white++;
                blue++;
                nums[blue] = 2;
                nums[white] = 1;
                nums[red] = 0;
            }
            else if(nums[i] == 1)
            {
                white++;
                blue++;
                nums[blue] = 2;
                nums[white] = 1;
            }
            else
            {
                blue++;
                nums[blue] = 2;
            }
        }
    }
};

Note

值得注意的是我们在写的时候，要把要插入的步骤写在其它数做完后移操作之后，因为存在一种可能假设现在整个数组中还不存在1，当你要插入0时，此时0和1的插入点是相同的，假设你先插入再后移，会使得插入的0被1替换掉（因为我们的后移操作是假设1的插入点前是1，0的插入点前是0），反之1被0替换则正确。

这种算法适合于已知数且不同数较少的排序，用替换取代后移，节省时间和空间。
时间复杂度和空间复杂度均为常数。