【算法专场】分治（上）

目录

前言

什么是分治？

75. 颜色分类

算法分析

算法步骤

算法代码

912. 排序数组 - 力扣（LeetCode）

算法分析

算法步骤

算法代码

215. 数组中的第K个最大元素 - 力扣（LeetCode）

算法分析

算法步骤

​编辑 

算法代码

LCR 159. 库存管理 III - 力扣（LeetCode） 

算法分析

算法步骤

算法代码

---

前言

在前面，我们学习了八大排序，那么其中的快速排序和归并排序都用到了分治的思想。在算法中，有时候我们也需要利用分治的思想来解决一些算法问题。本篇我们主要讲解快速排序。

什么是分治？

分治算法是一种算法设计策略，将大问题转化为小问题，再将小问题转化为更小的问题，通过解决子问题来大问题。也就是说，把问题分解成若干个规模较小的问题，然后通过递归的方法来解决这些子问题，最后将子问题合并起来得到想要的结果。

步骤：

1. 分解：将问题分解成若干个较小且独立的子问题，一般是通过递归实现；
2. 解决：分解成小问题之后，在每个子问题中解决问题需求
3. 归并：把问题解决完之后，将子问题进行合并。

接下来，我们就来通过一些练习来加深对分治思想的理解。

75. 颜色分类

算法分析

这道题的话就是要求我们将0、1、2这三个数依次从小排到大，那么对于这道题的话，其实我们有好几种排序方法都可以解决这道题，甚至我们可以使用java中的Arrays.sort()方法都可以解决，但是这里是不允许的。我们这里可以使用分治的思想来解决这道题。

算法步骤

算法代码

class Solution {/*** 交换数组中的两个元素* * @param arr 数组* @param left 左侧元素的索引* @param right 右侧元素的索引*/public void swap(int[] arr, int left, int right) {int tmp = arr[left];arr[left] = arr[right];arr[right] = tmp;}/*** 对颜色进行排序，将0放到数组的左边，2放到数组的右边，1保持原位* * @param nums 需要排序的颜色数组，其中的颜色用0、1、2表示*/public void sortColors(int[] nums) {int n = nums.length;int i = 0, left = -1, right = n;// 遍历数组，根据元素的值进行交换，最终达到0在左边，2在右边的目的while (i < right) {if (nums[i] == 0) {swap(nums, i++, ++left);} else if (nums[i] == 2) {swap(nums, i, --right);} else {i++;}}}
}

时间复杂度为O(n),空间复杂度为O(1). 

912. 排序数组 - 力扣（LeetCode）

算法分析

对于这种排序的题目，其实我们有很多种排序的方法可以解决，但是我们这里只讲如何使用分治的思想来解决这些排序题。 

算法步骤

对于这道题，我们可以采用分治的思想来解决，将数组划分为n个子数组，并且在n个子数组中使用类似快排的步骤来进行排序。同时我们需要注意：快排在趋近有序的情况下的时间复杂度为O(n^2),所以我们可以采用优化方法，如三数取中法，随机取值方法，这里我们采用的是随机取值法，使得算法的时间步骤度降为O(N*logN)

算法代码

/*** Solution 类用于提供一种基于快速排序的数组排序解决方案*/
class Solution {/*** 对数组进行快速排序* * @param nums 待排序的整数数组* @return 排序后的数组*/public int[] sortArray(int[] nums) {qsort(nums, 0, nums.length - 1);return nums;}/*** 交换数组中两个指定位置的元素* * @param nums 整数数组* @param left 左侧位置索引* @param right 右侧位置索引*/public void swap(int[] nums, int left, int right) {int temp = nums[left];nums[left] = nums[right];nums[right] = temp;}/*** 使用快速排序算法对数组进行排序* * @param nums 待排序的整数数组* @param left 排序开始的左边界索引* @param right 排序结束的右边界索引*/public void qsort(int[] nums, int left, int right) {if (left >= right) return;int key = nums[new Random().nextInt(right - left + 1) + left];int i = left, L = left - 1, R = right + 1;while (i < R) {if (nums[i] < key) swap(nums, ++L, i++);else if (nums[i] == key) i++;else swap(nums, i, --R);}qsort(nums, left, L);qsort(nums, R, right);}
}

215. 数组中的第K个最大元素 - 力扣（LeetCode）

算法分析

这道题其实就是TOP-K问题，我们可以使用优先级队列（堆）的方法来解决这个问题：首先我们可以创建一个小根堆，在这个小根堆中放入k个元素，接着遍历剩余的n-k个元素，查看堆顶元素是不是小于数组中的元素，若小于则进行替换。当然，我们这里主要讲分治思想，那么我们同样是利用快排来解决这道题。

算法步骤

算法代码

/*** Solution类用于解决寻找数组中第k大的元素的问题*/
class Solution {/*** 寻找数组中第k大的元素* * @param nums 输入的整数数组* @param k 指定的第k大元素* @return 数组中第k大的元素*/public int findKthLargest(int[] nums, int k) {// 调用快速排序相关函数来寻找第k大的元素return qsort(nums, 0, nums.length - 1, k);}/*** 快速排序算法的实现，用于寻找第k大的元素* * @param nums 输入的整数数组* @param l 排序区间的左边界* @param r 排序区间的右边界* @param k 指定的第k大元素* @return 第k大的元素*/private int qsort(int[] nums, int l, int r, int k) {// 如果左右指针相遇，直接返回该位置的元素if(l == r) return nums[l];// 随机选择一个基准值int key = nums[new Random().nextInt(r - l + 1) + l];int left = l - 1, right = r + 1, i = l;// 分区过程，将数组分为三部分：小于基准值的、等于基准值的和大于基准值的while(i < right) {if(nums[i] < key) swap(nums, ++left, i++);else if(nums[i] > key) swap(nums, i, --right);else i++;}// 根据分区结果，决定下一步的查找范围int b = right - left - 1; // 等于基准值的区域大小int c = r - right + 1; // 大于基准值的区域大小if(c >= k) return qsort(nums, right, r, k); // 如果第k大在大于基准值的区域else if(b + c >= k) return key; // 如果第k大在等于基准值的区域return qsort(nums, l, left, k - b - c); // 否则在小于基准值的区域继续查找}/*** 交换数组中两个元素的位置* * @param nums 输入的整数数组* @param i 第一个元素的索引* @param j 第二个元素的索引*/private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}

LCR 159. 库存管理 III - 力扣（LeetCode）

算法分析

本道题其实与前面的找第k个最大元素类似，我们依旧可以使用排序，然后有另一个数组记录[0,k]期间的数，但本道题我们可以采用分治的思想，利用快排来解决。

算法步骤

当我们完成上述的过程后，我们需要利用一个大小为k的数组ret来接收nums数组中【0，k】区间的数.

算法代码

class Solution {/*** 库存管理函数，通过快速排序算法对库存进行管理** @param stock 库存数据数组* @param cnt 需要管理的库存项数量* @return 管理后的库存数组*/public int[] inventoryManagement(int[] stock, int cnt) {// 使用快速排序对库存数组进行排序qsort(stock, 0, stock.length - 1, cnt);// 创建一个新的数组来存储管理后的库存数据int[] ret = new int[cnt];// 将排序后的库存数据的前cnt个元素复制到新的数组中for(int i=0;i<cnt;i++) {ret[i] = stock[i];}// 返回管理后的库存数组return ret;}/*** 交换数组中两个元素的位置** @param nums 数组* @param left 左侧元素索引* @param right 右侧元素索引*/public void swap(int[] nums, int left, int right){int temp = nums[left];nums[left] = nums[right];nums[right] = temp;}/*** 快速排序算法的实现** @param nums 待排序的数组* @param left 排序开始的左侧索引* @param right 排序结束的右侧索引* @param k 需要管理的库存项数量，用于决定排序的范围*/private void qsort(int[] nums, int left, int right, int k){if(left >= right) return;int key = nums[new Random().nextInt(right - left + 1) + left];int i = left, L = left - 1, R = right + 1;while(i < R){if(nums[i]<key) swap(nums,++L,i++);else if(nums[i]==key) i++;else swap(nums,i,--R);}// 根据分区结果，决定下一步的查找范围int a=L-left+1;int b=R-L-1;if(a>=k) qsort(nums,left,L,k);else if(a+b>=k) return;else qsort(nums,R,right,k-a-b);}
}

---

以上就是采用分治思想使用快排的一些题目。

本篇就先到这里啦~下一篇将为大家讲解采用归并排序如何解决一些算法题目。

若有不足，欢迎指正~