二分/手撕平衡树/分治/stable_sort

字数统计: 2k字 | 阅读时长: 8分

2022-03-25

摘要: 综合题：二分、平衡树、分治、stable_sort 四种解法

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

本文我们看一个排序的变种问题。跟排序一样，本题的解法也非常多，并且每个算法都是主流算法，除了平衡树以外，其它的算法代码量都不大，很适合面试。涉及到的算法如下：

二分
平衡树
分治
stable_sort

其中第四个 stable_sort 本质上就是第三个算法: 分治，因为在 STL 中 stable_sort 是归并排序。注意不能用 sort，因为快速排序不能保证最坏情况下只需要调用 $O(N\log N)$ 次 compare。

问题

113. 特殊排序

有 N 个元素，编号 1,2..N，每一对元素之间的大小关系是确定的，关系具有反对称性，但不具有传递性。

注意：不存在两个元素大小相等的情况。

也就是说，元素的大小关系是 N 个点与 N * (N−1) / 2 条有向边构成的任意有向图。

然而，这是一道交互式试题，这些关系不能一次性得知，你必须通过不超过 10000 次提问来获取信息，每次提问只能了解某两个元素之间的关系。

现在请你把这 N 个元素排成一行，使得每个元素都小于右边与它相邻的元素。

你可以通过我们预设的 bool 函数 compare 来获得两个元素之间的大小关系。

例如，编号为 a 和 b 的两个元素，如果元素 a 小于元素 b，则 compare(a,b) 返回 true，否则返回 false。

将 N 个元素排好序后，把他们的编号以数组的形式输出，如果答案不唯一，则输出任意一个均可。

1 2	数据范围 1<=N<=1000

题解

算法1: 二分

答案数组为 result。

数学归纳法：

如果当前 result 为空，则直接将当前元素加入 result 中。
假设 result 中已经加入了 k - 1 个元素，且已经排好序，只要能确定当前元素应该放在 result 中的 k - 1 个元素中的哪一个前面，即可将 k 正确插入。

一共要在 vec 中插入 N 个数，寻找插入位置的过程是二分的，需要调用 $O(\log N)$ 次 compare 接口。总共需要 $O(N\log N)$ 次。

代码 (C++)

class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int> vec;
        vec.push_back(1);
        for(int i = 2; i <= N; ++i)
        {
            int left = 0, right = vec.size();
            while(left < right)
            {
                int mid = (left + right) / 2;
                int j = vec[mid];
                if(compare(i, j))
                {
                    // i < j
                    right = mid;
                }
                else
                {
                    // j < i
                    left = mid + 1;
                }
            }
            vec.insert(vec.begin() + left, i);
        }
        return vec;
    }
};

算法2: 手撕平衡树

平衡树的思路还是很直接的：维护一棵平衡树，一个元素一个元素地插入，比较一下，把小的插到左子树，大的插入右子树。

所有元素插入完成后，前序遍历一下即可得到答案。

平衡树选择自己熟悉的一种即可，我们此前实现过两个: SBT 和 Treap，它们的算法细节和实现可以参考下面两篇文章

这里我们用 Treap，上面的文章中的代码模板中有很多功能，但是本题我们只需要少数功能，简化很多。下面是几个简化的点

Treap 的操作这里我们只需要 insert 即可。
这里我们不涉及小于 val 的元素个数，以及第 k 大元素的查询，因此节点的 size 字段不需要。
这里我们保证没有重复元素，因此节点中的 cnt 字段不需要。
需要额外实现一下二叉树的前序遍历即可。

一共要在 treap 中插入 N 个数，从根节点找到插入位置(某个叶子节点)需要调用 compare 的次数为树的高度，对于平衡树，为$O(\log N)$。总共需要调用 $O(N\log N)$ 次。

代码(C++，Treap)

struct TreapNode
{
    int val;
    int w;
    TreapNode *left, *right;
    TreapNode():w(rand()),left(nullptr),right(nullptr){}
};

class Treap
{
public:
    Treap():root(nullptr){}
    ~Treap()
    {
        delete_sub_tree(root);
    }

    void insert(int val)
    {
        insert(val, root);
    }

    vector<int> preOrder()
    {
        vector<int> result;
        _preOrder(root, result);
        return result;
    }

private:
    TreapNode *root;

    void _preOrder(TreapNode* node, vector<int>& result)
    {
        if(node -> left)
            _preOrder(node -> left, result);
        result.push_back(node -> val);
        if(node -> right)
            _preOrder(node -> right, result);
    }

    void zig(TreapNode*& p)
    {
        // 右旋
        TreapNode *tmp = p -> left;
        p -> left = tmp -> right;
        tmp -> right = p;
        p = tmp;
    }

    void zag(TreapNode*& p)
    {
        // 左旋
        TreapNode *tmp = p -> right;
        p -> right = tmp -> left;
        tmp -> left = p;
        p = tmp;
    }

    void insert(int val, TreapNode*& p)
    {
        if(p == nullptr)
        {
            p = new TreapNode();
            p -> val = val;
            return;
        }
        // compare(a,b) 若 a < b 则返回 true，否则返回 false。
        if(compare(p -> val, val))
        {
            insert(val, p -> right);
            if(p -> w < p -> right -> w)
                zag(p);
        }
        else
        {
            insert(val, p -> left);
            if(p -> w < p -> left -> w)
                zig(p);
        }
    }

    void delete_sub_tree(TreapNode* p)
    {
        if(p -> left)
            delete_sub_tree(p -> left);
        if(p -> right)
            delete_sub_tree(p -> right);
        delete p;
        p = nullptr;
    }
};

class Solution {
public:
    vector<int> specialSort(int N) {
        Treap treap = Treap();
        for(int i = 1; i <= N; ++i)
            treap.insert(i);
        return treap.preOrder();
    }
};

算法3: 分治

这里我们要对 1 ~ N 排序，因此也可以用分解-解决-合并这种分治的思路。

分解: 待排序区间为 [l, r] 时，分解为 [l, (l + r) / 2], [(l + r) / 2 + 1, r]

解决: 如果区间长度为 1，直接返回即可

合并: 两个子区间均已排好序后，走一遍数组的两路归并即可

上面是正常的归并排序的过程，归并排序的算法细节和实现代码可以参考下面的文章。

数组排序

在上面的分解-解决-合并的分治标准流程中，比较的操作是在合并的过程进行的。由于每次分解时，区间都是对半分的，根据主定理，一共会分 $O(\log N)$ 层。每一层在合并的过程中要进行 $O(N)$ 次比较，因此总共需要 $O(N\log N)$ 次比较。

这里我们只需要在数组的归并排序的代码中，将比较的部分改为调用 compare 即可，一共需要调用 $O(N\log N)$ 次。

代码(C++) 手撕归并排序

void _merge(vector<int>& nums, int low, int mid, int high)
{
    // 归并时候的辅助数组
    vector<int> tmp(high - low + 1, 0);

    int i = low, j = mid, k = 0;
    while(i < mid && j <= high)
    {
        if(compare(nums[i], nums[j]))
        {
            tmp[k] = nums[i];
            ++k;
            ++i;
        }
        else
        {
            tmp[k] = nums[j];
            ++k;
            ++j;
        }
    }
    while(i < mid) tmp[k++] = nums[i++];
    while(j <= high) tmp[k++] = nums[j++];
    for(k = 0, i = low; i <= high; ++k, ++i)
        nums[i] = tmp[k];
}

void _mergesort_topdown(vector<int>& nums, int low, int high)
{
    int mid = low + (high - low) / 2;
    if(low == high) return;
    _mergesort_topdown(nums, low, mid);
    _mergesort_topdown(nums, mid + 1, high);
    _merge(nums, low, mid + 1, high); // 归并左右两个有序表
}

// 归并排序, 两种实现方式, 这里用自顶向下
void mergesort(vector<int>& nums)
{
    if(nums.empty()) return;
    int n = nums.size();
    if(n == 1) return;
    _mergesort_topdown(nums, 0, n - 1);
}

class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int> vec(N);
        for(int i = 1; i <= N; ++i)
            vec[i - 1] = i;
        mergesort(vec);
        return vec;
    }
};

算法4：STL stable_sort

<algorithm> 中的 stable_sort 是归并排序。前面我们手撕了归并排序，也可以直接用 stable_sort 即可。

代码(C++)

class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int> vec(N);
        for(int i = 1; i <= N; ++i)
            vec[i - 1] = i;
        stable_sort(vec.begin(), vec.end(), compare);
        return vec;
    }
};

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

算法疑难杂症