[LeetCode] 75. Sort Colors 顏色排序

Given an array with n objects colored red, white or blue, sort them in-place 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.

Example:

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

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 a one-pass algorithm using only constant space?

這道題的本質(zhì)還是一道排序的題，題目中給出提示說可以用計數(shù)排序，需要遍歷數(shù)組兩遍，那么先來看這種方法，因為數(shù)組中只有三個不同的元素，所以實現(xiàn)起來很容易。

- 首先遍歷一遍原數(shù)組，分別記錄 0，1，2 的個數(shù)。
- 然后更新原數(shù)組，按個數(shù)分別賦上 0，1，2。

解法一：

class Solution {
public:
    void sortColors(vector<int>& nums) {
        vector<int> colors(3);
        for (int num : nums) ++colors[num];
        for (int i = 0, cur = 0; i < 3; ++i) {
            for (int j = 0; j < colors[i]; ++j) {
                nums[cur++] = i;
            }
        }
    }
};

題目中還要讓只遍歷一次數(shù)組來求解，那么就需要用雙指針來做，分別從原數(shù)組的首尾往中心移動。

- 定義 red 指針指向開頭位置，blue 指針指向末尾位置。

- 從頭開始遍歷原數(shù)組，如果遇到0，則交換該值和 red 指針指向的值，并將 red 指針后移一位。若遇到2，則交換該值和 blue 指針指向的值，并將 blue 指針前移一位。若遇到1，則繼續(xù)遍歷。

解法二：

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

當然我們也可以使用 while 循環(huán)的方式來寫，那么就需要一個變量 cur 來記錄當前遍歷到的位置，參見代碼如下：

解法三：

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int left = 0, right = (int)nums.size() - 1, cur = 0;
        while (cur <= right) {
            if (nums[cur] == 0) {
                swap(nums[cur++], nums[left++]);
            } else if (nums[cur] == 2) {
                swap(nums[cur], nums[right--]);
            } else {
                ++cur;
            }
        }
    }
};

到此這篇關于C++實現(xiàn)LeetCode(75.顏色排序)的文章就介紹到這了,更多相關C++實現(xiàn)顏色排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論