【LeetCode】75. Sort Colors解法及注释

怼烎@ 2022-07-26 08:48 138阅读 0赞

**75. Sort Colors**

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.

【分析】

初见之下，一个最明显的思路就是“计数排序”，或者说“桶排序”，因为需要排序的数据很集中，存在大量重复，即便数据很多，实际上也就三种情况，我们只需要两次遍历便可解决问题：一次遍历记录下0,1,2出现的次数，第二次，将数组中对应的位置为0,1或者2。

【解法及注释】

class Solution {
    public:
        void sortColors(vector<int>& nums) {
            
            int numOfColor[3]={0};//记录0,1,2出现的次数
            
            for(int i=0;i<nums.size();i++)
            {
                switch(nums[i])
                {
                    case 0:numOfColor[0]++;break;
                    case 1:numOfColor[1]++;break;
                    case 2:numOfColor[2]++;break;
                    default:return;
                }
            }
            nums.
            for(int i=0;i<nums.size();i++)
            {
                if(i<numOfColor[0])nums[i]=0;
                else if(i>=numOfColor[0]&&i<numOfColor[1]+numOfColor[0])nums[i]=1;
                else nums[i]=2;
            }
        }
    };

既然是初见之下想到的方法，很多时候都不是最好的解法，网上大牛给出了一个很精妙的解法：采用“平移”，滑动添加，如此仅需一次遍历便可完成排序，膜拜之余，给出其算法如下：\[注\]：这个方法虽然精妙，但是在LeetCode上的运行效率并没有比上面的方法好多少，主要原因应该是赋值的次数太多，频繁读写数据。

class Solution {
    public:
        void sortColors(vector<int>& nums) {
            
            int i = -1;
            int j = -1;
            int k = -1;
            for(int p = 0; p < nums.size(); p ++)
            {
                //根据第i个数字，挪动0~i-1串。
                if(nums[p] == 0)
                {
                    nums[++k] = 2;    //2往后挪
                    nums[++j] = 1;    //1往后挪
                    nums[++i] = 0;    //0往后挪
                }
                else if(nums[p] == 1)
                {
                    nums[++k] = 2;
                    nums[++j] = 1;
                }
                else
                    nums[++k] = 2;
            }
    
        }
    };