【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){left++;swap(nums,i,left);i++;}else if(nums[i] == key){i++;}else 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<Integer> minHeap = new PriorityQueue<>();for(int i = 0;i<k;i++){minHeap.offer(nums[i]);}//剩余元素for(int i = k;i<nums.length;i++){if(nums[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){left ++;swap(nums,i,left);i++;}else if(nums[i] == key){i++;}else 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;}
}

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