LeetCode75——Sort Colors

简要的分析一下题意就是对只包含 0,1,2 这三个数的数组进行排序。

这里提供三种方案，前两种是自己Y出来的，后一种是大神的解法。

方案一：

计数排序：

具体思路参见《算法导论》

代码最后有一个O(n)复杂度的拷贝，原因是题目用引用参数的方式对容器数组返回。

代码：

class Solution {
public:
    void sortColors(vector<int>& nums) {
        vector<int>B(nums.size()+1,0);
        vector<int>C(3, 0);
        for (int i = 0; i < nums.size(); i++)
        {
            C[nums[i]] = C[nums[i]] + 1;
        }
        for (int i = 1; i < 3; i++)
        {
            C[i] = C[i] + C[i - 1];
        }
        for (int i = nums.size() - 1; i >= 0; i--)
        {
            B[C[nums[i]]] = nums[i];
            C[nums[i]] = C[nums[i]] - 1;
        }
        for (int i = 1; i < nums.size()+1; i++)
        {
            nums[i-1] = B[i];
        }
    }
};

方案二：

构建辅助数组count[]，该数组用来统计 0,1,2的个数（时间复杂度 O(n) ）

通过这个辅助数组，向数组中相应个数的0，1，2

代码：

class Solution {
public:
    void sortColors(vector<int>& nums) {
        vector<int>count(3, 0);//只有0,1,2 辅助数组大小为3，初始全为0
        for (int i = 0; i < nums.size(); i++)
        {
            count[nums[i]]++;
        }
        nums.clear();//清空
        for (int i = 0; i < count.size(); i++)
        {
            int j = 0;
            while (j < count[i])
            {
                nums.push_back(i);
                j++;
            }
        }
    }
};

方案三：

参考code ganker的博客http://blog.csdn.net/linhuanmars/article/details/24286349

具体思路是维护两个索引。因为最后排出来的效果肯定是00…000111…1111222…2222这样。

这两个索引：

index0记录0分段的最后一个0出现的位置。

index1记录1分段的最后一个1出现的位置。

当然这两个索引是实时更新的。

代码：

class Solution{
public:
    void sortColors(vector<int>& nums) {
        int index0 = 0;
        int index1 = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            if (nums[i] == 0)
            {
                nums[i] = 2;
                nums[index1++] = 1;
                nums[index0++] = 0;
            }
            else if (nums[i] == 1)
            {
                nums[i] = 2;
                nums[index1++] = 1;
            }
        }
    }
};