0%

相关的编程题汇总-分治

发表于 更新于 分类于 ，

记录了分治算法类的题目，最常见的 快排，归并排序中都使用了分治的思想

分治算法

快速排序

快速排序的核心思想是在待排序数组中选取一个 基准数据（原则上要尽量保证 基准数据正好是中位数，这里以常用的第一个元素作为基准数据，基准数据选的不好 算法的复杂度会达到O(n^2)，但是平均复杂度趋近O(N)）。首先以数组第一个元素为基准a，将大于a的元素都放在a的右边，小于的放在左边。再递归的在左右区间使用这种策略直至排序完成。具体的伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 inline int randomPartition(vector<int>& a, int l, int r) {
        int i = rand() % (r - l + 1) + l;
        swap(a[i], a[r]);
        return partition(a, l, r);
    }
//双指针 划分 数组
    inline int partition(vector<int>& a, int l, int r) {
        int x = a[r], i = l - 1;
        for (int j = l; j < r; ++j) {
            if (a[j] <= x) {
                swap(a[++i], a[j]);
            }
        }
        swap(a[i + 1], a[r]);
        return i + 1;
    }

求无序数组的第K大

这个题 可以暴力的将数组先 排序 完后取出。但是不是最好方法，可以使用快速排序 （分治）的方法，取基准数 按照与基准数的大小关系将数组划分左右，后判断 基准数左边有几个大于它的元素，再分别选择对左边 或者右边 数组进行再一次的 快排，直到 正好找到第K个。 ​ 求K大问题除了使用快排之外，还可以使用 堆的 方法。

颜色分类

这个题 数组中其实 只有 0，1， 2 三种元素。不能使用额外的空间。最直观的想法是，先使用 基准元素 1 将数组划分为 左边的 0/1 右边的2，再设置基准为0前半部分 将0，1分开。这就是最朴素的 快排的思想。但是，因为只有三种元素，可以考虑 使用三个指针，一个指针移动负责遍历所有元素，一个左指针寻找0的最右边边界，一个右指针寻找2的最左边边界。当前指向的元素等于0就和左指针交换元素，并且滑动一个位置，同理。这就和快排中 将数组中元素根据 与基准数据的大小关系分堆类似。

为运算表达式设计优先级

这个题很典型的分治 算法。将 运算符 看作 分隔点，每次计算运算符左边的 字符串表达的等式的值 和 右边的字符串表达的算式的值，最后 使用该运算符计算二者的 和/差/积 即为最终的一种结果。但是注意 左边字符串算出的 值 可能有多个 使用 vector 保存 右边的也是。所以计算的时候需要两个for循环。

不同的二叉搜索树 II

首先 这个题 二叉搜索树的特点是 中序遍历输出的为有序 数组。所以 要将1~n的 数组还原为二叉搜索树，就是 选定根节点，然后 按照中序遍历的特点 分别递归的构建左右子树，也是分治的思想。要注意递归的停止边界条件。

归并排序

数组中的逆序对

根据逆序对的定义，会想到 这个比较过程 可以通过归并排序的过程等效转换，因为归并过程中存在前半部分 和 后半部分比较的过程，且前半部分和后半部分都是有序的，因此速度快。

小和问题

计算右侧小于当前元素的个数

这个和逆序数问题很像，所以直接用归并排序的思路求解即可。