算法基础算法

三色排序

字数统计: 2.4k字   |   阅读时长: 11分
, ,

摘要: 计数排序的特例：三色排序

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们通过一个模板题看一下三色排序问题。有计数排序和双指针两种方法。之后我们解决力扣 324 摆动排序2，其中的一步可以抽象为三色排序解决。力扣 280 摆动排序是简化版，直接用于 324 相同的三色排序可以解决，此外也可以用贪心解决。

三色排序

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

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

必须在不使用库内置的 sort 函数的情况下解决这个问题。

提示：

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

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

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

进阶：

你能想出一个仅使用常数空间的一趟扫描算法吗？

算法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
25
26
27
28
29
class Solution {
public:
    void sortColors(vector<int>& nums) {
        _countingsort(nums);
    }

private:
    // 基本计数排序
    void _countingsort(vector<int>& nums)
    {
        if(nums.empty()) return;
        int n = nums.size();
        if(n == 1) return;

        // 数据范围 0-2
        // 计数排序空间复杂度 O(N + K), K = 3
        int K = 3;
        vector<int> cnt(K, 0);
        for(int i = 0; i < n; ++i)
            ++cnt[nums[i]];

        for(int i = 0, k = 0; i < K; ++i)
            while(cnt[i] > 0)
            {
                nums[k++] = i;
                --cnt[i];
            }
    }
};

算法2：双指针

双指针, 类似快速排序中单指针 partition 的操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    void sortColors(vector<int>& nums) {
        _twopointers(nums);
    }

private:
    // 双指针
    // 类似单指针 partition 的操作
    void _twopointers(vector<int>& nums)
    {
        if(nums.empty()) return;
        int n = nums.size();
        if(n == 1) return;

        int left = 0, right = n - 1; // n >= 2, right >= 1
        // left 的左侧都是 0, right 的右侧都是 2
        for(int i = 0; i <= right;)
        {
            if(nums[i] == 0)
                swap(nums[i++], nums[left++]);
            else if(nums[i] == 2)
                swap(nums[i], nums[right--]);
            else
                ++i;
        }
    }
};

摆动排序II

给你一个整数数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]… 的顺序。

你可以假设所有输入数组都可以得到满足题目要求的结果。

提示：

1
2
3
1 <= nums.length <= 5e4
0 <= nums[i] <= 5000
题目数据保证，对于给定的输入 nums ，总能产生满足题目要求的结果

示例 1：
输入：nums = [1,5,1,1,6,4]
输出：[1,6,1,5,1,4]
解释：[1,4,1,5,1,6] 同样是符合题目要求的结果，可以被判题程序接受。

示例 2：
输入：nums = [1,3,2,2,3,1]
输出：[2,3,1,3,1,2]

算法：排序 + 下标映射

基本思路：先排序，再映射一下。

映射过程如下：

1
2
偶数下标：用前半段，从大到小
奇数下标：用后半段，也从大到小

例如:

  • 0,1,2,3,4,5,6，映射后成为 3,6,2,5,1,4,0;
  • 0,1,2,3,4,5,6,7，映射后成为 3,7,2,6,1,5,0,4

先排序再映射是基本法，但是在排序之后再映射就不好写了，因为额外空间只有 $O(1)$。

因此需要排序阶段直接在原坐标 i 映射后的坐标 f(n, i) 上运算。在枚举元素、划分区间的时候用原索引 i，而涉及元素操作，包括比较，交换等，用映射后的索引 f(i, n)。

这有点类似索引数组的思想:

用索引数组的思路理解这里的映射 f(n, i): 给定答案数组的下标 f(n, i)，其值是原数组(排序后的数组)的下标 i 的元素，即 indexes[f(n, i)] = i, result[f(n, i)] = nums[indexes[f(n, i)]]。这里根索引数组的做法是反向的，索引数组的做法是给定答案数组的元素，追溯它原数组中的位置；映射的做法是给定原数组的位置，追溯它对应的答案数组的值。

比较难的是映射函数怎么写，因为要分奇偶讨论:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int f(int i, int n) // 坐标映射
{
    // 假id(做排序的id) -> 真实应该放到的 id
    // 偶数长度 3,7,2,6,1,5,0,4
    // 奇数数长度 4,8,3,7,2,6,1,5,0
    // i <= (n - 1)/2 的放下面, i >= (n - 1)/2 + 1 放上面
    if(n % 2 == 0)
    {
        if(i <= (n - 1) / 2)
            return n - 2 - i * 2;
        else
            return n - 1 - (i - (n + 1) / 2) * 2;
    }
    else
    {
        if(i <= (n - 1) / 2)
            return n - 1 - i * 2;
        else
            return n - 2 - (i - (n + 1) / 2) * 2;
    }
}

排序使用快排无 partition 版本，在访问原始数据的地方 nums[i] 都加上映射 nums[f(i, n)]。

代码(c++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        if(nums.empty()) return;
        int n = nums.size();
        if(n == 1) return;

        quicksort(nums);
    }

private:
    void quicksort(vector<int> &nums)
    {
        if(nums.empty()) return;
        int n = nums.size();
        if(n == 1) return;
        _quicksort3(nums, 0, n - 1);
    }

    // 快排最短模板, 不带 partition
    void _quicksort3(vector<int>& nums, int l, int r)
    {
        int n = nums.size();

        if(l >= r) return;
        int i = l - 1, j = r + 1, x = nums[f((l + r) >> 1, n)];// pivot 取中间点的值已经很好了，随机更好
        while(i < j)
        {
            do j--; while(nums[f(j, n)] > x);
            do i++; while(nums[f(i, n)] < x);
            if(i < j) swap(nums[f(i, n)], nums[f(j, n)]);
            else _quicksort3(nums, l, j), _quicksort3(nums, j + 1, r); // 这一行代替了 partition
        }
    }

    int f(int i, int n) // 坐标映射
    {
        // 假id(做排序的id) -> 真实应该放到的 id
        // 偶数长度 3,7,2,6,1,5,0,4
        // 奇数数长度 4,8,3,7,2,6,1,5,0
        // i <= (n - 1)/2 的放下面, i >= (n - 1)/2 + 1 放上面
        if(n % 2 == 0)
        {
            if(i <= (n - 1) / 2)
                return n - 2 - i * 2;
            else
                return n - 1 - (i - (n + 1) / 2) * 2;
        }
        else
        {
            if(i <= (n - 1) / 2)
                return n - 1 - i * 2;
            else
                return n - 2 - (i - (n + 1) / 2) * 2;
        }
    }
};

优化：三色排序 + 下标映射

不需要全排序，只需要按照大于中位数，等于中位数，小于中位数排序, 变成了三色排序问题。因为原数组只需要排成 [小于中位数，中位数，大于中位数]，其映射后的数组就满足摆动的条件了。

找到中位数的过程，相当于求第 k 大，这是一个专题，参考 力扣215-快速选择算法,划分树，这里直接用 std::nth_element。

三色排序是计数排序的应用，其算法过程参考： 非比较排序。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        if(nums.empty()) return;
        int n = nums.size();
        if(n == 1) return;

        _threecolorsort(nums);
    }

private:
    void _threecolorsort(vector<int>& nums)
    {
        int n = nums.size();
        nth_element(nums.begin(), nums.begin() + n / 2, nums.end());
        int mid = nums[n / 2];

        int left = 0, right = n - 1;
        int l = left, r = right, cur = left;
        // [left, l)   < mid
        // [l, cur)    = mid
        // [cur, r]    未处理
        // (r, right]  > mid
        while(cur <= r)
        {
            if(nums[f(cur, n)] < mid)
                swap(nums[f(cur++, n)], nums[f(l++, n)]);
            else if(nums[f(cur, n)] == mid)
                ++cur;
            else
                swap(nums[f(cur, n)], nums[f(r--, n)]);
        }
    }

    int f(int i, int n) // 坐标映射
    {
        // 假id(做排序的id) -> 真实应该放到的 id
        // 偶数长度 3,7,2,6,1,5,0,4
        // 奇数数长度 4,8,3,7,2,6,1,5,0
        // i <= (n - 1)/2 的放下面, i >= (n - 1)/2 + 1 放上面
        if(n % 2 == 0)
        {
            if(i <= (n - 1) / 2)
                return n - 2 - i * 2;
            else
                return n - 1 - (i - (n + 1) / 2) * 2;
        }
        else
        {
            if(i <= (n - 1) / 2)
                return n - 1 - i * 2;
            else
                return n - 2 - (i - (n + 1) / 2) * 2;
        }
    }
};

摆动排序

给你一个的整数数组 nums, 将该数组重新排序后使 nums[0] <= nums[1] >= nums[2] <= nums[3]…

输入数组总是有一个有效的答案。

提示：

1
2
3
1 <= nums.length <= 5e4
0 <= nums[i] <= 1e4
输入的 nums 保证至少有一个答案。

示例 1:
输入：nums = [3,5,2,1,6,4]
输出：[3,5,1,6,2,4]
解释：[1,6,2,5,3,4]也是有效的答案

示例 2:
输入：nums = [6,6,5,6,3,8]
输出：[6,6,5,6,3,8]

进阶：你能在 O(n) 时间复杂度下解决这个问题吗？

算法：贪心

本题于前面的 324. 摆动排序 II 除了 < 改成 <=、> 改成 >=，其它完全一样。

我们贪心地处理每个索引 i：

  • 如果 i 是偶数，nums[i] 应该小于或等于 nums[i + 1]。如果 nums[i] > nums[i + 1]，我们交换 nums[i] 和 nums[i + 1]。
  • 如果 i 是奇数，nums[i] 应该大于或等于 nums[i + 1]。如果 nums[i] < nums[i + 1]，我们交换 nums[i] 和 nums[i + 1]。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        int n = nums.size();
        if(n <= 1) 
            return;

        // n >= 2
        for(int i = 1; i < n; ++i)
        {
            // if(i % 2 == 1 && nums[i] < nums[i - 1])
            //    swap(nums[i], nums[i - 1]);
            // if(i % 2 == 0 && nums[i] > nums[i - 1])
            //    swap(nums[i], nums[i - 1]);

            // 简化写法
            if ((i % 2 == 0) == (nums[i] > nums[i + 1]))
                swap(nums[i], nums[i - 1]);
        }
    }
};
Share