专题七——分治算法

2024-10-26 07:12:40

一分治-快排

1颜色划分

2快速排序

3第K个最大数

4最小的k个数

二分治-归并

1归并排序

2交易逆序对的总数

3计算右侧小于当前元素的个数

4翻转对

一分治-快排

1颜色划分

oj链接：颜色分类

思路：三指针

类似双指针的移动零：搞三个指针来划分0,1,2区间

i:遍历数组(以它来分析)

left:标记0的最右侧

right:标记2的最左侧

接下来就是划分区间来讨论

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

2快速排序

oj链接：排序数组

思路：三指针

数组分为三个区间

i:遍历数组(以它来分析)

left:标记<key的最右侧

right:标记>key的最左侧

接下来就是划分区间来讨论

优化：用随机的方式选择key值

也就是先种一颗随机数种子srand(time(NULL))

key = nums[ rand()%(r-l+1) + l ] (每次递归区间元素个数不同，l也是不同)

class Solution
{
public:
    vector<int> sortArray(vector<int> &nums)
    {
        srand(time(NULL));
        QuickSort(nums, 0, nums.size() - 1);
        return nums;
    }
    void QuickSort(vector<int> &nums, int l, int r)
    {
        if (l >= r)
            return;
        int key = nums[rand() % (r - l + 1) + l], left = l - 1, right = r + 1;
        for (int i = left + 1; i < right;)
        {
            if (nums[i] < key)
                swap(nums[++left], nums[i++]);
            else if (nums[i] == key)
                i++;
            else
                swap(nums[--right], nums[i]);
        }
        QuickSort(nums, l, left);
        QuickSort(nums, right, r); // r+1 x i到达r位置停止该位置的数=还是>key是不确定的！
    }
};

3第K个最大数

oj链接：数组中的第K个最大元素

除了要用到上面的思想，还要在递归之前分类讨论！

class Solution
{
public:
    int findKthLargest(vector<int> &nums, int k)
    {
        srand(time(NULL));
        return QucikSort(nums, 0, nums.size() - 1, k);
    }
    int QucikSort(vector<int> &nums, int l, int r, int k)
    {
        if (l == r)
            return nums[l]; // l==r 保证区间是存在的!
        int key = nums[rand() % (r - l + 1) + l], left = l - 1, right = r + 1;
        for (int i = l; i < right;) // i<r X
        {
            if (nums[i] < key)
                swap(nums[++left], nums[i++]); // left++ X
            else if (nums[i] == key)
                i++;
            else
                swap(nums[--right], nums[i]); // right-- X
        }
        int b = right - left - 1, c = r - right + 1; // b个数的区间 [left+1,right-1]
        if (c >= k)
            return QucikSort(nums, right, r, k);
        else if (b + c >= k)
            return key;
        else
            return QucikSort(nums, l, left, k - b - c);
    }
};

4最小的k个数

oj链接：库存管理 III

与上题类似，但有细节：a > k不用 a==k：因为a == k直接返回就行了不用在找了！

class Solution {
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt) 
    {
        srand(time(NULL));
        QuickSlectSort(stock,0,stock.size()-1,cnt);
        return {stock.begin(),stock.begin()+cnt};
    }
    void QuickSlectSort(vector<int>& stock,int l,int r,int k)
    {
        if(l>=r) return;
        int left=l-1,right=r+1,i=l;
        int key=stock[rand()%(r-l+1)+l];
        while(i<right)
        {
            if(stock[i]<key) swap(stock[i++],stock[++left]);
            else if(stock[i]>key) swap(stock[i],stock[--right]);
            else i++;
        }
        //分情况
        int a=left-l+1,b=right-left-1,c=r-right+1;
        if(a>k) QuickSlectSort(stock,l,left,k);
        else if(a+b>=k) return;
        else QuickSlectSort(stock,right,r,k-a-b); 
    }
};

二分治-归并

1归并排序

oj链接：排序数组

class Solution {
public:
    vector<int> tmp;
    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)
    {
        if(left>=right) return;//一个数向上返回
        int mid=left+(right-left)/2;
        MergeSort(nums,left,mid);
        MergeSort(nums,mid+1,right);

        int cur1=left,cur2=mid+1,i=0;//i从0开始
        while(cur1<=mid && cur2<=right)
        {
            tmp[i++]=nums[cur1]<nums[cur2]?nums[cur1++]:nums[cur2++];
        }
        while(cur1<=mid) tmp[i++]=nums[cur1++];
        while(cur2<=right) tmp[i++]=nums[cur2++];

        for(int i=left;i<=right;i++) nums[i]=tmp[i-left];
    }
};

2交易逆序对的总数

oj链接：交易逆序对的总数

策略：把数组分为2段区间：

1.到左区间找找逆序对后排序

2.到右区间找找逆序对后排序

3.左右区间找找逆序对后排序

可以自己画图来看看结果对不对

其实这个过程就是归并排序的过程

class Solution {
public:
    vector<int> tmp;
    int reversePairs(vector<int>& record) 
    {
        tmp.resize(record.size());
        return MergeSort(record,0,record.size()-1);
    }
    int MergeSort(vector<int>& record,int l,int r)
    {
        if(l>=r) return 0;
        int mid=l+(r-l)/2;
        int cnt=0;
        cnt+=MergeSort(record,l,mid);
        cnt+=MergeSort(record,mid+1,r);

        int cur1=l,cur2=mid+1,i=0;
        while(cur1<=mid&&cur2<=r)
        {
            if(record[cur1]<=record[cur2])
            {
                tmp[i++]=record[cur1++];
            }
            else
            {
                //升序
                cnt+=mid-cur1+1;
                tmp[i++]=record[cur2++];
            }
        }
        while(cur1<=mid) tmp[i++]=record[cur1++];
        while(cur2<=r) tmp[i++]=record[cur2++];

        for(int j=l;j<=r;j++) record[j]=tmp[j-l];
        return cnt;
    }

};

class Solution {
public:
    vector<int> tmp;
    int reversePairs(vector<int>& record) 
    {
        tmp.resize(record.size());
        return MergeSort(record,0,record.size()-1);
    }
    int MergeSort(vector<int>& record,int l,int r)
    {
        if(l>=r) return 0;
        int mid=l+(r-l)/2;
        int cnt=0;
        cnt+=MergeSort(record,l,mid);
        cnt+=MergeSort(record,mid+1,r);

        int cur1=l,cur2=mid+1,i=0;
        while(cur1<=mid&&cur2<=r)
        {
            if(record[cur1]<=record[cur2])
            {
                tmp[i++]=record[cur2++];
            }
            else
            {
                //降序
                cnt+=r-cur2+1;
                tmp[i++]=record[cur1++];
            }
        }
        while(cur1<=mid) tmp[i++]=record[cur1++];
        while(cur2<=r) tmp[i++]=record[cur2++];

        for(int j=l;j<=r;j++) record[j]=tmp[j-l];
        return cnt;
    }

};

3计算右侧小于当前元素的个数

oj链接：计算右侧小于当前元素的个数

解法：

1.使用上题的策略2：当前元素的后面有多少个比我小

2.关键是当前元素对应的原始数组下标我怎么知道？

有哈希表进行下标绑定？ --> 解决不了重复元素的问题

做法：用哈希表的思想创建index数组(保存元素下标)与元素进行绑定

那么在归并时就需要用到两个辅助数组进行归并

class Solution {
public:
    vector<int> tmpnum;
    vector<int> tmpindex;
    vector<int> ret;
    vector<int> index;
    vector<int> countSmaller(vector<int>& nums) 
    {
        int n=nums.size();
        tmpnum.resize(n),tmpindex.resize(n);
        ret.resize(n),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(right<=left) return;
        int mid=left+(right-left)/2;
        MergeSort(nums,left,mid);
        MergeSort(nums,mid+1,right);

        int cur1=left,cur2=mid+1,i=0;
        while(cur1<=mid&&cur2<=right)//降序
        {
            if(nums[cur1]<=nums[cur2])
            {
                tmpnum[i]=nums[cur2];
                tmpindex[i++]=index[cur2++];
            } 
            else
            {
                ret[index[cur1]]+=right-cur2+1;

                tmpnum[i]=nums[cur1];
                tmpindex[i++]=index[cur1++];
            }
        }
        while(cur1<=mid)
        {
            tmpnum[i]=nums[cur1];
            tmpindex[i++]=index[cur1++];
        }
        while(cur2<=right)
        {
            tmpnum[i]=nums[cur2];
            tmpindex[i++]=index[cur2++];
        }
        for(int i=left;i<=right;i++)
        {
            nums[i]=tmpnum[i-left];
            index[i]=tmpindex[i-left];
        }
    }
};

4翻转对

oj链接：翻转对

与前2道题类似：注意翻转对的条件：nums[i] > 2*nums[j]

这个就不能很好的与归并排序匹配了！

但解决思路也是一样：在归并两个有序数组之前进行统计即可（就不是变合变统计）

class Solution {
public:
    int ret=0;
    vector<int> tmp;
    int reversePairs(vector<int>& nums) 
    {
        tmp.resize(nums.size());
        MergeSort(nums,0,nums.size()-1);
        return ret;
    }
    void MergeSort(vector<int>& nums,int l,int r)
    {
        if(l>=r) return;
        int mid=l+(r-l)/2;
        MergeSort(nums,l,mid);
        MergeSort(nums,mid+1,r);
        int cur1=l,cur2=mid+1,i=0;

        int ptr1=cur1,ptr2=cur2;
        while(ptr1<=mid)
        {
            while(ptr2<=r&&nums[ptr1]<=2*(long long)nums[ptr2]) ptr2++;
            ret+=r-ptr2+1;
            ptr1++;
            
        }

        while(cur1<=mid&&cur2<=r)
        {
            tmp[i++]=nums[cur1]<=nums[cur2]?nums[cur2++]:nums[cur1++];//降序
        }
        while(cur1<=mid) tmp[i++]=nums[cur1++];
        while(cur2<=r) tmp[i++]=nums[cur2++];
        for(int i=l;i<=r;i++) nums[i]=tmp[i-l];
    }
};

以上便是全部内容，有错误欢迎在评论区指正，感谢你的观看！

码农公寓

一分治-快排

1颜色划分

2快速排序

3第K个最大数

4最小的k个数

二分治-归并

1归并排序

2交易逆序对的总数

3计算右侧小于当前元素的个数

4翻转对

相关文章