【leetcode】拆解与整合：分治并归的算法逻辑

前言

🌟🌟本期讲解关于力扣的几篇题解的详细介绍~~~

🌈感兴趣的小伙伴看一看小编主页：GGBondlctrl-CSDN博客

🔥 你的点赞就是小编不断更新的最大动力                                       

🎆那么废话不多说直接开整吧~~

目录

📚️1.颜色分类

🚀1.1题目分析

🚀1.2思路分析

🚀1.3代码实现

📚️2.数组排序（双重解法）

🚀2.1题目分析

🚀2.2思路分析

2.2.1分治思想

2.3.2分治并归

🚀2.3代码实现

2.3.1分治思想 

2.3.2分治并归

📚️3.数组中第K个最大元素

🚀3.1题目分析

🚀3.2思路分析

3.2.1建立小根堆

3.2.2分治思想

🚀3.3代码实现

3.3.1建立小根堆思想

3.3.2分治思想

📚️4.总结

📚️1.颜色分类

🚀1.1题目分析

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

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

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

所以换一句话总结来说，就是将这里的数组进行排序，相邻的数字挨在一起；

即如上图所示；

🚀1.2思路分析

这不就简单了吗，哈哈哈，小编的思路如下所示；

第一种：直接通过八大排序，随便取一种进行排序即可；

第二种：通过模拟哈希的方式，记录0下标有几个数，然后1下标有几个数，2下标有几个                      数，最后循环遍历输出就可以了；

第三种：就是我们以分治的思想，将整个数组拆成三份；

 当然小编本期讲解的就是第三种思想方法；

具体是思路：

我们将数组分成三份，第一部分就是小于1的，第二部分就是等于1的，第三部分就是大于1的；

那么使用双指针，分别在左右两端，指针i负责遍历数组，那么如果出现0就与left进行交换，1就直接跳过，2就与right进行交换；

图示如下：

注意：在这里我们为啥在num[ i ] 大于1后，为啥交换后，i不用增加呢？其实我们并不知道right指针所指的值，那么交换到i指针位置后，所以i指针需要继续进行判断；

核心：

num[ i ] < 1：left++，交换，i++;

num[ i ] ==1:  i++;

num[ i ] > 1:  right--，交换 

🚀1.3代码实现

代码如下所示：

class Solution { public void sortColors(int[] nums) { int left = -1; int right = nums.length; for(int i = 0; i < right;){ if(nums[i] == 0){ swap(nums,++left,i); i++; }else if(nums[i] == 2){ swap(nums,--right,i); }else{ i++; } } } public void swap(int[] nums,int left,int right){ int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; }}

解释：注意这里的跳出循环条件，和初始化left与right的值，以及对于数组来说，这里的交换是如何进行的；

📚️2.数组排序（双重解法）

🚀2.1题目分析

其实看题目就知道，这里就是对于数组进行排序的操作，如下所示：

OK小编也不再多说了，直接进行入正题

🚀2.2思路分析

2.2.1分治思想

其实这里的思路和上面进行分治的操作的思想是一致，将原始的数组进行分治三份进行后，元素就分为三个部分，其中等于某一个key值后，我们就不用管这个等于key的部分了，左边都是小于key的，右边都是大于key的，那么我们再对于这两个部分进行分治的操作；

一直进行分治操作下，若只剩下两个数字，那么分治过后必定是有序的；那么总结：

在不断的分治过程中，等于key的部分不用管，那么不等于key的两边部分一直进行分治操作，那么最终就会变得有序；

那么这就是分治分三块思想可以完成次题的具体步骤；

2.3.2分治并归

这里的操作其实其实小编在很早的时候就已经讲解过了，就是快排的思想；

不断的拆分，直到为一个数字的时候进行合并的操作，这里的合并的操作就是比较重要的；在每次合并的时候进行排序，那么在最终合成后，整个数组就是一个有序的数组；

那么最终就是如上图所示，即可完成本此的排序操作；

🚀2.3代码实现

2.3.1分治思想 

代码如下所示：

class Solution { public int[] sortArray(int[] nums) { qsort(nums, 0 ,nums.length - 1); return nums; } public void qsort(int nums[],int l,int r){ if(l>=r){ return; } //随机进行取值的操作 int key = nums[new Random().nextInt(r - l + 1) + l]; int left = l - 1; int right = r + 1; int i = l; //进行三块分类排序的操作 while(i < right){ if(nums[i]  key){ right--; swap(nums,i,right); } } //排序完成后分为三部分[l,left][left+1,right-1][right,r] qsort(nums,l,left); qsort(nums,right,r); } public void swap(int nums[],int left,int right){ int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; }}

注意：这里的交换条件，以及边界的情况；

2.3.2分治并归

代码如下所示：

class Solution { public int[] sortArray(int[] nums) { //归并排序操作 mergeSort(nums,0,nums.length - 1); return nums; } public void mergeSort(int[] nums,int left,int right){ //进行边界判断 if(left >= right){ return; }  //获取中点 int mid = (right + left)/2; //此时[left,mid][mid + 1,right] mergeSort(nums,left,mid); mergeSort(nums,mid + 1 ,right); int[] temp = new int[right - left + 1]; //合并数据操作 int cur1 = left; int cur2 = mid + 1; int i = 0; while(cur1 <= mid && cur2 <= right){ if(nums[cur1] <= nums[cur2]){ temp[i] = nums[cur1]; i++; cur1++; }else{ temp[i] = nums[cur2]; i++; cur2++; } } //判断是否还存在元素 while(cur1 <= mid){ temp[i] = nums[cur1]; i++; cur1++; } while(cur2 <= right){ temp[i] = nums[cur2]; i++; cur2++; } //最后进行还原操作 for(int j = left;j <= right;j++){ nums[j] = temp[j-left]; } }}

注意在进行合并的时候，谁更小，谁就先放置在预备数组里；最终有一个数组是没有遍历完的，直接进行插入就可以了，前面有讲大家可以去看看；【数据结构】关于快速排序，归并排序，计数排序，基数排序，你到底了解多少？？？（超详解）_对比基数排序和快速排序-CSDN博客

📚️3.数组中第K个最大元素

🚀3.1题目分析

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题

其实这里就是topk问题，那么小编就不多进行解释了

🚀3.2思路分析

其实这里的思路有几种：

第一种：使用排序算法，在遍历寻找；

第二种：建立小根堆，实现查找；

第三种：使用分治的思想，分为三部分，来进行讨论；

 小编这里将讲解一下第一种和第二种算法思想：

3.2.1建立小根堆

具体的思路如下所示：

按照K个长度的小根堆，然后将剩下的数字与堆顶元素进行比较，如果大于对顶元素，那么就将对顶元素删除，将这个大于对顶元素的值加入到堆中；

 最终堆顶的元素就是第K大的元素了；

3.2.2分治思想

思路如下：

在我们分为三个部分后，那么第k大的元素就落在这三个部分中的一个；落在最右边，那么就去最右边去查找第K大的元素，落在中间直接返回，因为中间部分都是相等的数字；落在最左边，那么就去最左边找数字；

如下所示：

那么以上就是本题的结题思路；

🚀3.3代码实现

3.3.1建立小根堆思想

代码如下所示：

class Solution { public int findKthLargest(int[] nums, int k) { //实现小根堆 PriorityQueue minHeap = new PriorityQueue(); for(int i = 0;i<k;i++){ minHeap.offer(nums[i]); } //剩余元素 for(int i = k;i minHeap.peek()){ minHeap.poll(); minHeap.offer(nums[i]); } } return minHeap.peek(); }

 当然这也是绝大多数的方法，也是比较简单的一种；

3.3.2分治思想

代码如下：

class Solution { public int findKthLargest(int[] nums, int k) { // 快速选择算法 return quickSort(nums, 0, nums.length - 1, k); } public int quickSort(int nums[],int l,int r,int k){ if(l == r){ return nums[l]; } //进行随机key值的获取 int key = nums[new Random().nextInt(r - l + 1) + l]; //进行变量的赋值 int right = r + 1; int left = l - 1; int i = l; //进行选取 while(i < right){ if(nums[i]  key){ right --; swap(nums,i,right); } } int b = right - left - 1; int c = r - right + 1; if(c >= k){ return quickSort(nums,right,r,k); }else if(b+c >= k){ return key; }else{ return quickSort(nums,l,left,k-b-c); } } public void swap(int nums[],int left,int right){ int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; }}

解释：其实这里和前面数组的排序几乎是一致的，就是在进行分治的时候，需要进行判断在那个区间进行分治操作；

📚️4.总结

本期小编主要讲解了关于leetcode中的题目：

颜色分类（75. 颜色分类 - 力扣（LeetCode））

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

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

主要的思想就是分治与并归的思想，大家可以多刷刷；

🌅🌅🌅~~~~最后希望与诸君共勉，共同进步！！！

💪💪💪以上就是本期内容了， 感兴趣的话，就关注小编吧。

       😊😊  期待你的关注~~~