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

用户11288949

发布于 2025-03-30 20:19:59

1550

文章被收录于专栏：学习学习

📚️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;
    }
}

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