Leetcode: Sort Colors

红太狼 2022-08-07 12:47 111阅读 0赞

题目：  
Given an array with n objects colored red, white or blue, sort them 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.

思路分析：  
题目出了这样的提示：  
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 an one-pass algorithm using only constant space?

按照提示two-pass算法代码如下，这个比较简单。  
C++参考代码：

class Solution { 
    public:
        void sortColors(int A[], int n)
        {
            int count[3] = {
       0};
            for (int i = 0; i < n; i++)
            {
                if (0 == A[i]) count[0] += 1;
                else if (1 == A[i]) count[1] += 1;
                else if (2 == A[i]) count[2] += 1;
            }
            int x = count[0] + count[1];
            int y = x + count[2];
            for (int i = 0; i < n; i++)
            {
                if (i < count[0]) A[i] = 0;
                else if (i < x) A[i] = 1;
                else if (i < y) A[i] = 2;
            }
        }
    };

那什么是所谓的one-pass算法呢？

我们可以定义两个指针：一个指针left指向当前应该插入0的位置，一个指针right指向当前应该插入2的位置，再利用一个指针current进行循环遍历。遇到0的时候就插入left的位置，left前进一位，遇到2的时候就插入right的位置，right后退一位，遇到1的时候，current前进一位。

C++参考代码：

class Solution
    {
    public:
        void sortColors(int A[], int n)
        {
            int left = 0;
            int right = n - 1;
            int current = 0;
            //注意这里是<=不是<
            while (current <= right)
            {
                if (0 == A[current])
                {
                    swap(A[current], A[left]);
                    ++left;
                    //处理left可能大于current的情况
                    current = left > current ? left : current;
                }
                else if (2 == A[current])
                {
                    swap(A[current], A[right]);
                    --right;
                }
                else
                {
                    ++current;
                }
            }
        }
    };