【算法百题】专题七_分治快排_专题八_分治归并

发布于：2025-03-18 ⋅ 阅读:(19) ⋅ 点赞:(0)

文章目录

前言

分治顾名思义,就是分而治之,分治是一个思路,并不是由暴力优化而来的,还是因为暴力解的重复比较太多,我们可以将大问题划分为小问题(当然不是无厘头的划分),每次分割后，子问题的规模呈指数级缩小（理想情况下减半），总操作次数从 O(n^2) 降至 O(nlogn).

在这里插入图片描述

分治快排题：

043. 颜⾊分类（medium）

分析

在这里插入图片描述

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int left = -1,right = nums.size();
        int i = 0;
        while(i < right)
        {
            if(nums[i] < 1) swap(nums[++left],nums[i++]);
            else if(nums[i] > 1) swap(nums[--right],nums[i]);
            else i++;
        }
    }
};

044. 快速排序（medium）

分析

在这里插入图片描述

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) 
    {
        srand(time(nullptr));
        qsort(nums,0,nums.size()-1);
        return nums;
    }

    void qsort(vector<int>& nums,int l,int r)
    {
        //3.然后再写"归"的逻辑,如果只有一个值,一个值也是有序的,那么直接返回,不用排了.
        //if(r - l + 1 == 1) return; 逻辑没错,但是有可能出现l 比 r大的情况
        if(l >= r) return;

        //1.这里分治用的是快排的方向,所以先将我们的数组进行划分,然后再递归子区间.
        int key = getRandNum(nums,l,r);              //随机找一个数作为key,避免有序情况的爆栈
        int i = l;
        int left = l - 1,right = r + 1;
        while(i < right)                                //然后开始将数组根据key值进行划分
        {
            if(nums[i] < key) swap(nums[++left],nums[i++]);
            else if(nums[i] > key) swap(nums[--right],nums[i]);
            else i++;
        }

        //2.递归递归,当然要先写向深处"递"的逻辑.
        qsort(nums,l,left);
        qsort(nums,right,r);
    }

    int getRandNum(vector<int>& nums,int l,int r)
    {
        int x = rand();
        return nums[x % (r - l + 1) + l];
    }
};

045. 快速选择算法（medium）

分析

在这里插入图片描述

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        srand(time(nullptr));
        return qsort(nums,0,nums.size()-1,k);
        
    }

    int qsort(vector<int>& nums,int l,int r,int k)
    {
        if(l >= r) return nums[l];

        int key = getRandpm(nums,l,r);

        int i = l;
        int left = l - 1,right = r + 1;
        while(i < right)
        {
            if(nums[i] < key) swap(nums[++left],nums[i++]);
            else if(nums[i] > key) swap(nums[--right],nums[i]);
            else i++;
        }
        
        if(r - right + 1 >= k) return qsort(nums,right,r,k);     //优化再递归思路这里,不用全部递归,可以根据大概的左右子区间的元素个数,判断一下我们的topK最终会在什么区间,时间复杂度是O(N).
        else if(r - left >= k) return key;
        else return qsort(nums,l,left,k - (r - left));

    }

    int getRandpm(vector<int>& nums,int l,int r)
    {
        return nums[rand() % (r - l + 1) + l];
    }
};

046. 仓库管理

分析

在这里插入图片描述

class Solution {
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt) 
    {
        srand(time(nullptr));
        qsort(stock,0,stock.size() - 1,cnt);
        return {stock.begin(),stock.begin() + cnt};
    }

    void qsort(vector<int>& stock,int l,int r,int cnt)
    {
        if( l >= r) return;

        int key = getRandom(stock,l,r);
        int i = l,left = l - 1,right = r + 1;
        while(i < right)
        {
            if(stock[i] < key) swap(stock[++left],stock[i++]);
            else if(stock[i] > key) swap(stock[--right],stock[i]);
            else i++;
        }

        int a = left - l + 1,b = right - left - 1,c = r - right + 1;  //我们快排本来就是在原数组上面做操作,所以走完逻辑其实原数组也就拍好了
        if(a >= cnt) qsort(stock, l,left,cnt);
        else if(a + b >= cnt) return ;
        else qsort(stock, right,r,cnt - a - b);
    }

    int getRandom(vector<int>& stock,int l,int r)
    {
        return stock[l + rand() % (r - l + 1)];
    }
};

分治归并题

047. 归并排序（medium）

分析

在这里插入图片描述

class Solution {
    vector<int> tmp; //我们合并的过程中,需要一个单独的容器暂时存储.
public:
    vector<int> sortArray(vector<int>& nums) {
        tmp.resize(nums.size());
        mergeSort(nums,0,nums.size()-1);
        return nums;
    }

    void mergeSort(vector<int>& nums,int left,int right)
    {
        //2.然后写"归"的逻辑,不然即使"递"到了最深处,即[l,r]区间的只有一个数据时,也不会停下.
        if(left >= right) return;    //只有一个数据时,也是有序的.

        //1.从数组的中间开始划分,先"递"到最深处.
        int mid = (right + left) >> 1;   
        mergeSort(nums,left,mid);
        mergeSort(nums,mid + 1,right);

        //3.然后开始每个组 合并的逻辑
        int x = left;
        int i = left,j = mid + 1;
        while(i <= mid && j <= right)
        {
            if(nums[i] <= nums[j]) tmp[x++] = nums[i++];
            else tmp[x++] = nums[j++];
        }

        while(i <= mid)  //如果小组里面还有没合并完的大组,那么,直接放入tmp.
        {
            tmp[x++] = nums[i++];
        }
        while(j <= right)
        {
            tmp[x++] = nums[j++];
        }

        //将tmp数据同步回原数组,那么我们的一次合并就完成了.
        for(int i = left;i <= right;i++)
        {
            nums[i] = tmp[i]; 
        }
    }
};

048. 数组中的逆序对（hard）

分析

在这里插入图片描述

class Solution 
{
    int tmp[50010];
public:
    int reversePairs(vector<int>& record) 
    {
        return mergeSort(record,0,record.size()-1);
    }
    int mergeSort(vector<int>& nums,int left,int right)
    {
        //2.写"归"的逻辑,让它在停在有两个最小组的层.方便我们对两个最小组中的值做刚开始的逆序对判断.
        if(left >= right) return 0;

        int ret = 0;

        //1.先"递"到最小
        int mid = (left + right) >> 1;
        ret += mergeSort(nums,left,mid);
        ret += mergeSort(nums,mid + 1,right);
        
        //3.合并同时做判断,找到所有符合的逆序对
        int cur1 = left,cur2 = mid + 1,i = left;
        while(cur1 <= mid && cur2 <= right)
        {
            if(nums[cur2] >= nums[cur1])
            {
                tmp[i++] = nums[cur1++];
            }
            else
            {
                ret += mid - cur1 + 1;
                tmp[i++] = nums[cur2++];
            }
        }

        
        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= right) tmp[i++] = nums[cur2++];

        //4.将tmp中排序好的顺序数组,覆盖回原数组.
        for(int i = left;i <= right;i++)
        {
            nums[i] = tmp[i];
        }
        return ret;
    }
};

049. 计算右侧⼩于当前元素的个数（hard）

分析

在这里插入图片描述

class Solution {
    vector<int> ret;
    vector<int> index;

    int tmp[100010];
    int tmpIndex[100010];
public:
    vector<int> countSmaller(vector<int>& nums)
    {
        int n = nums.size();
        ret.resize(n,0);
        index.resize(n);

        for(int i = 0;i < n;i++)
            index[i] = i;
        
        mergeSort(nums,0,n-1);
        return ret;
    }

    void mergeSort(vector<int>& nums,int left,int right)
    {
        if(left >= right) return;

        int mid = (left + right) >> 1;

        mergeSort(nums,left,mid);
        mergeSort(nums,mid + 1,right);

        int cur1 = left,cur2 = mid + 1,i = left;
        while(cur1 <= mid && cur2 <= right)
        {
            if(nums[cur1] > nums[cur2])
            {
                ret[index[cur1]] += right - cur2 + 1;
                tmp[i] = nums[cur1];
                tmpIndex[i++] = index[cur1++];
            }
            else
            {
                tmp[i] = nums[cur2];
                tmpIndex[i++] = index[cur2++];
            }
        }

        while(cur1 <= mid) 
        {
            tmp[i] = nums[cur1];
            tmpIndex[i++] = index[cur1++];
        }
        while(cur2 <= right) 
        {
            tmp[i] = nums[cur2];
            tmpIndex[i++] = index[cur2++];
        }

        //将临时的下标数组和原数组都同步回去.
        for(int i = left;i <= right;i++)
        {
            nums[i] = tmp[i];
            index[i] = tmpIndex[i];
        }
    }
};

050. 计算右侧⼩于当前元素的个数（hard）

分析

在这里插入图片描述

class Solution {
    int tmp[50010];
public:
    int reversePairs(vector<int>& nums) 
    {
        return mergeSort(nums,0,nums.size() - 1);
    }
    
    int mergeSort(vector<int>& nums,int left,int right)
    {
        //2."归"
        if(left >= right) return 0;

        int ret = 0;

        //1.先"递"
        int mid = (left + right) >> 1;
        ret += mergeSort(nums,left,mid);
        ret += mergeSort(nums,mid + 1,right);
        
        //2.1统计所有翻转对.
        int cur1 = left,cur2 = mid + 1,i = left;
        while(cur2 <= right)
        {
            while(cur1 <= mid && nums[cur1] / 2.0 <= nums[cur2]) cur1++;
            if(cur1 > mid) break;
            ret += mid - cur1 + 1;
            cur2++;
        }


        cur1 = left,cur2 = mid + 1;
        //3.排序并判断翻转对
        while(cur1 <= mid && cur2 <= right)
        {
            if(nums[cur1] <= nums[cur2])
            {
                tmp[i++] = nums[cur1++];
            }
            else
            {
                tmp[i++] = nums[cur2++];
            }
        }

        //4.将没有排完的排完
        while(cur1 <= mid)
        {
            tmp[i++] = nums[cur1++];
        }
        while(cur2 <= right)
        {
            tmp[i++] = nums[cur2++];
        }

        //5.将排好的数组覆盖原数组.
        for(int i = left;i <= right;i++)
        {
            nums[i] = tmp[i];
        }
        return ret;
    }
};

总结

分治的思路,远不止这两种,将问题划分小也不总是针对一个数组的(动规也是分治思想的延伸),但是本专题,针对数组的划分,尽量理解"我们是一名老师,让孩子们站队"的例子.

本文章为作者的笔记和心得记录，顺便进行知识分享，有任何错误请评论指点：）。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布