Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[LeetCode] 75. Sort Colors #75

Open
grandyang opened this issue May 30, 2019 · 1 comment
Open

[LeetCode] 75. Sort Colors #75

grandyang opened this issue May 30, 2019 · 1 comment

Comments

@grandyang
Copy link
Owner

grandyang commented May 30, 2019


请点击下方图片观看讲解视频
Click below image to watch YouTube Video
Video

Given an array nums 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.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library's sort function.

Example 1:

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

Example 2:

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

Constraints:

  • n == nums.length
  • 1 <= n <= 300
  • nums[i] is either 0, 1, or 2.

Follow up: Could you come up with a one-pass algorithm using only constant extra space?

这道题说是给了三种颜色,red,white,和 blue,分别用数字0,1,2来表示,现在让给这些颜色排序,要使得相同的颜色挨在一起,并且是以 red,white,和 blue 的顺序进行排序。本质上还是一道排序的题,题目中给出提示说可以用计数排序,需要遍历数组两遍,那么先来看这种方法,因为数组中只有三个不同的元素,所以实现起来很容易。

- 首先遍历一遍原数组,分别记录 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;
            }
        }
    }
};

Github 同步地址:

#75

类似题目:

Sort List

Wiggle Sort II

Wiggle Sort

参考资料:

https://leetcode.com/problems/sort-colors/

https://leetcode.com/problems/sort-colors/discuss/26500/Four-different-solutions

https://leetcode.com/problems/sort-colors/discuss/26472/Share-my-at-most-two-pass-constant-space-10-line-solution

https://leetcode.com/problems/sort-colors/discuss/26760/C%2B%2B-solution-in-8-lines%3A-an-instance-of-the-Dutch-national-flag-problem-by-Edsger-Dijkstra

LeetCode All in One 题目讲解汇总(持续更新中...)

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,快快加入吧~)

知识星球 喜欢请点赞,疼爱请打赏❤️~.~

微信打赏

|

Venmo 打赏


---|---

@jimbinc
Copy link

jimbinc commented Aug 14, 2020

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants