廖家龙的博客网站
LeetCode_75_颜色分类
廖家龙 用心听，不照做
  2019-06-30 19:56:00   2024-07-19 11:20:33    248 字  1 分钟

题目描述：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//经典的「荷兰国旗问题」，考察如何对三个重复且打乱的值进行排序

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

示例：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

输入：nums = [2,0,1]
输出：[0,1,2]

输入：nums = [0]
输出：[0]

输入：nums = [1]
输出：[1]

提示：
1. n == nums.length
2. 1 <= n <= 300
3. nums[i] 为 0、1 或 2

解法1：快速排序思想

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    void sortColors(vector<int>& nums) {

        int l = 0,r = nums.size() - 1;

        int i = 0;

        while (i <= r) {  //注意边界条件是i <= r

            if (nums[i] == 0) swap(nums[i++],nums[l++]);
            
            else if (nums[i] == 1) i++;

            else if (nums[i] == 2) swap(nums[i],nums[r--]);
        }
    }
};
  1. 1. 题目描述：
    1. 1.1. 解法1：快速排序思想
  1. 1. 题目描述：
    1. 1.1. 解法1：快速排序思想