C++怎么實(shí)現(xiàn)顏色排序

這篇文章主要介紹了C++怎么實(shí)現(xiàn)顏色排序的相關(guān)知識(shí)，內(nèi)容詳細(xì)易懂，操作簡單快捷，具有一定借鑒價(jià)值，相信大家閱讀完這篇C++怎么實(shí)現(xiàn)顏色排序文章都會(huì)有所收獲，下面我們一起來看看吧。

顏色排序

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ì)還是一道排序的題，題目中給出提示說可以用計(jì)數(shù)排序，需要遍歷數(shù)組兩遍，那么先來看這種方法，因?yàn)閿?shù)組中只有三個(gè)不同的元素，所以實(shí)現(xiàn)起來很容易。

- 首先遍歷一遍原數(shù)組，分別記錄 0，1，2 的個(gè)數(shù)。
- 然后更新原數(shù)組，按個(gè)數(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ù)組的首尾往中心移動(dòng)。

- 定義 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--]);
            } 
        }
    }
};

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

解法三：

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;
            }
        }
    }
};

關(guān)于“C++怎么實(shí)現(xiàn)顏色排序”這篇文章的內(nèi)容就介紹到這里，感謝各位的閱讀！相信大家對(duì)“C++怎么實(shí)現(xiàn)顏色排序”知識(shí)都有一定的了解，大家如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道。