当前位置:首页 > 综合 > 综合

LintCode-色彩分类

优良自学吧提供LintCode-色彩分类,LintCode-颜色分类给定一个包含红,白,蓝且长度为n的数组,将数组元素进行分类使相同颜色的元素相邻,并按照红、白、蓝的顺序进行排序。 我们可以使用整数0,1和2分别代表红,白,蓝。 样例 注意 不能使用代码库中的排序函数来解决这个问题 说明 一个相当直接的解决方案是使用计数排序扫描2遍的算法。 首

LintCode-颜色分类

给定一个包含红,白,蓝且长度为n的数组,将数组元素进行分类使相同颜色的元素相邻,并按照红、白、蓝的顺序进行排序。

我们可以使用整数0,1和2分别代表红,白,蓝。

样例
注意

不能使用代码库中的排序函数来解决这个问题

说明

一个相当直接的解决方案是使用计数排序扫描2遍的算法。

首先,迭代数组计算0,1,2出现的次数,然后依次用0,1,2出现的次数去覆盖数组。

你否能想出一个仅使用常数级额外空间复杂度且只扫描遍历一遍数组的算法?


分析:可以类似快排一样,把0都放到最左边,把2都放到最右边,中间的自然而言就为1.

代码:

class Solution{
public:
    /**
     * @param nums: A list of integer which is 0, 1 or 2 
     * @return: nothing
     */    
    void sortColors(vector<int> &nums) {
        // write your code here
        int l = 0;
        int r = nums.size()-1;
        for(int i=0;i<min((int)nums.size(),r+1);)
        {
            if(nums[i]==0)
            {
                if(i==l)
                    i++;
                else
                    swap(nums[i],nums[l]);
                l++;
            }
            else if(nums[i]==2)
            {
                swap(nums[i],nums[r]);
                r--;
            }
            else
                i++;
        }
    }
};



(本文来自互联网,不代表搜站(http://www.ylzx8.cn/)的观点和立场)
本站所有内容来自互联网,若本站收录的信息无意侵犯了贵司版权,请给我们来信(ylzx8cn@163.com),我们会及时处理和回复,谢谢