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

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

翔安網(wǎng)站建設(shè)公司成都創(chuàng)新互聯(lián)公司,翔安網(wǎng)站設(shè)計(jì)制作，有大型網(wǎng)站制作公司豐富經(jīng)驗(yàn)。已為翔安成百上千提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\外貿(mào)網(wǎng)站制作要多少錢，請(qǐng)找那個(gè)售后服務(wù)好的翔安做網(wǎng)站的公司定做！

顏色排序

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)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

分享題目：C++怎么實(shí)現(xiàn)顏色排序
文章起源：http://muchs.cn/article4/jcjhoe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供小程序開發(fā)、用戶體驗(yàn)、靜態(tài)網(wǎng)站、定制開發(fā)、全網(wǎng)營(yíng)銷推廣、網(wǎng)站營(yíng)銷

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)