leetcode筆記：Sort Colors

leetcode筆記：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.

Follow up:
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?

二. 題目分析

題目一開始說到一組對象，包含紅白藍三種顏色，然後要對他們進行排序，說白了就是對一個只含有0, 1, 2三個數字的數組從小到大排序。

題目要求：come up with an one-pass algorithm using only constant space，因此只能掃描一次。這裡采取的方法是，統計0, 1, 2三個數字分別出現的次數，再將數組nums重新構建為從0到2排列的數組，這種方法沒有使用數組元素間的交換，只需掃描一次nums。

三. 示例代碼

#include 
#include 

using namespace std;

class Solution {
public:
    void sortColors(vector& nums) 
    {
        int SIZE = nums.size();
        int count[3] = {0, 0, 0};
        for (int i = 0; i < SIZE; ++i)
            ++count[nums[i]];

        for (int i = 0, index = 0; i < 3; ++i)
            for (int j = 0; j < count[i]; ++j)
                nums[index++] = i;
    }
};

一個測試結果：

四. 小結

本題的解法還是挺多的，可多參考網上的其他解法。