快捷導(dǎo)航

C++實(shí)現(xiàn)LeetCode(75.顏色排序)

更新時(shí)間：2021年07月17日 11:52:22 作者：Grandyang

這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(75.顏色排序),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

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

- 首先遍歷一遍原數(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ù)組來(lái)求解，那么就需要用雙指針來(lái)做，分別從原數(shù)組的首尾往中心移動(dòng)。

- 定義 red 指針指向開(kāi)頭位置，blue 指針指向末尾位置。

- 從頭開(kāi)始遍歷原數(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)的方式來(lái)寫(xiě)，那么就需要一個(gè)變量 cur 來(lái)記錄當(dāng)前遍歷到的位置，參見(jiàn)代碼如下：

解法三：

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)LeetCode(75.顏色排序)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)顏色排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: