C++怎么實現顏色排序

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

顏色排序

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?

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

- 首先遍歷一遍原數組，分別記錄 0，1，2 的個數。
- 然后更新原數組，按個數分別賦上 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;
            }
        }
    }
};

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

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

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

解法二：

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 循環的方式來寫，那么就需要一個變量 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++怎么實現顏色排序”這篇文章的內容就介紹到這里，感謝各位的閱讀！相信大家對“C++怎么實現顏色排序”知識都有一定的了解，大家如果還想學習更多知識，歡迎關注億速云行業資訊頻道。