wordpress添加文字广告框架,seo技术建站,上海公司推荐,最有前途的15个专业目录
前言
什么是分治#xff1f;
75. 颜色分类
算法分析
算法步骤
算法代码
912. 排序数组 - 力扣#xff08;LeetCode#xff09;
算法分析
算法步骤
算法代码
215. 数组中的第K个最大元素 - 力扣#xff08;LeetCode#xff09;
算法分析
算法步骤
编辑…
目录
前言
什么是分治
75. 颜色分类
算法分析
算法步骤
算法代码
912. 排序数组 - 力扣LeetCode
算法分析
算法步骤
算法代码
215. 数组中的第K个最大元素 - 力扣LeetCode
算法分析
算法步骤
编辑
算法代码
LCR 159. 库存管理 III - 力扣LeetCode
算法分析
算法步骤
算法代码 前言
在前面我们学习了八大排序那么其中的快速排序和归并排序都用到了分治的思想。在算法中有时候我们也需要利用分治的思想来解决一些算法问题。本篇我们主要讲解快速排序。
什么是分治
分治算法是一种算法设计策略将大问题转化为小问题再将小问题转化为更小的问题通过解决子问题来大问题。也就是说把问题分解成若干个规模较小的问题然后通过递归的方法来解决这些子问题最后将子问题合并起来得到想要的结果。
步骤
分解将问题分解成若干个较小且独立的子问题一般是通过递归实现解决分解成小问题之后在每个子问题中解决问题需求归并把问题解决完之后将子问题进行合并。
接下来我们就来通过一些练习来加深对分治思想的理解。
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数组中【0k】区间的数.
算法代码
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 i0;icnt;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 aL-left1;int bR-L-1;if(ak) qsort(nums,left,L,k);else if(abk) return;else qsort(nums,R,right,k-a-b);}
}以上就是采用分治思想使用快排的一些题目。
本篇就先到这里啦~下一篇将为大家讲解采用归并排序如何解决一些算法题目。
若有不足欢迎指正~
