Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Sort Colors

Leetcode algorithms 第 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.

解答

因为只有3个数进行排序,可以直接统计每个数出现的次数,然后把这三组数组合起来。

具体代码如下:

class Solution {
public:  
    void sortColors(int A[], int n) {
        int n1 = 0, n2 = 0, n3 = 0; //0 1 2出现的次数
        for (int i = 0; i < n; i++)
        {
            if (A[i] == 0) ++n1;
            else if(A[i] == 1) ++n2;
            else if (A[i] == 2) ++n3;
        }
        int i = 0;
        while (n1--) A[i++] = 0;
        while (n2--) A[i++] = 1;
        while (n3--) A[i++] = 2;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论