Vault 101

xjay2007's Blog

0%

LeetCode 75. 颜色分类

发表于 更新于 分类于 ， Valine：

题目描述

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

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

注意:
不能使用代码库中的排序函数来解决这道题。

示例:

1
2
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

进阶：

  • 一个直观的解决方案是使用计数排序的两趟扫描算法。
    首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
  • 你能想出一个仅使用常数空间的一趟扫描算法吗？

题解

两趟扫描

  • 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// C++
void sortColors(vector<int>& nums) {
    int zero = 0, one = 0, two = 0;
    for (auto it = nums.begin(); it != nums.end(); ++it) {
        auto n = *it;
        if (n == 0) {
            ++zero;
        } else if (n == 1) {
            ++one;
        } else {
            ++two;
        }
    }
    for (auto i = 0; i < nums.size(); ++i) {
        if (i < zero) {
            nums[i] = 0;
        } else if (i < zero + one) {
            nums[i] = 1;
        } else {
            nums[i] = 2;
        }
    }
}

三路快排

  • 划分三段，0放左段，2放右段 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// C++
void sortColors(vector<int>& nums) {
    // [0-zero]:0, [zero+1,i-1]:1, [i,two]:2
    int zero = -1;
    int two = (int)nums.size();
    int i = 0;
    while (i < two) {
        auto n = nums[i];
        if (n == 0) {
            swap(nums[i], nums[zero+1]);
            ++i;
            ++zero;
        } else if (n == 1) {
            ++i;
        } else {
            swap(nums[i], nums[two-1]);
            --two;
        }
    }
}

思路三

设置三个指针 i，j，k，分别指向当前已处理好的字符串的最后一个0，1，2。

比如，当前已处理好的字符串如下 ，那么 i，j，k分别指向最后一个0，1，2。m指向*，*号为待处理元素，

1
2
3
0000 111 222 *
   ^   ^   ^ ^
   i   j   k m

​ 那么 i, j, k 分别指向最后一个0，1，2. m指向下一个待处理元素。比如现在*的位置元素为 0 ，那么只需要把原来i，j，k所指元素的后面一个分别赋值成0，1，2。

参考链接：leetcode 75 分类颜色 / sort colours, by twt727.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// C++
void sortColors2(vector<int>& nums) {
    int i = -1, j = -1, k = -1;
    int size = (int)nums.size();
    for (auto m = 0; m < size; ++m) {
        auto n = nums[m];
        if (n == 0) {
            nums[++k] = 2;
            nums[++j] = 1;
            nums[++i] = 0;
        } else if (n == 1) {
            nums[++k] = 2;
            nums[++j] = 1;
        } else {
            nums[++k] = 2;
        }
    }
}
相似文章