【算法】利用分治思想解算法题:快排、归并、快速选择实战(C++)

2024-01-02 20:33:03

1. 分治思想 介绍

分治法将问题划分成多个相互独立且相同或类似的子问题,然后递归地解决每个子问题,并将结果合并以得到原始问题的解。

分治思想通常包含以下三个步骤:

  1. 分解:将原始问题划分成多个规模较小、相互独立且类似的子问题。这个步骤可以通过递归方法实现。
  2. 解决:递归地解决每个子问题。当子问题足够小而可以直接求解时,使用简单的方法解决。
  3. 合并:将各个子问题的解合并,得到原始问题的解。

核心思想

是将一个复杂的问题分解成多个简单的子问题,通过递归地解决子问题,最终将子问题的解合并成原始问题的解

我们也遇到过一些,例如:归并排序、快速排序、二叉树的遍历等。

优缺点

优点在于能够有效地降低问题的复杂度,提高算法的效率。缺点在于需要额外的空间和时间来处理子问题的合并过程。


2. 分治思想 引入

75.颜色分类

在这里插入图片描述
思路

  • 题意分析:数组中只有三种元素0、1、2,要求按照012的顺序对数组进行原地排序
  • 解法一:排序
    • 我们想当然的可以想到用排序解决,这个解法也不用多说
  • 解法二:三指针划分数组
    • 数组中只有三种元素,我们利用三个指针
      在这里插入图片描述
  • 如上图所示

代码

void sortColors(vector<int>& nums) {
    // 三个指针划分区域
    // [0, left-1] : 0
    // [left, i] : 1
    // [i, right-1] : 未检测
    // [right, n-1] : 2
    int left = -1, i = 0, right = nums.size();
    while(i < right) // i,right相遇,全部检索完成
    {
        if(nums[i] == 0){
            swap(nums[++left], nums[i++]);
        }else if(nums[i] == 1){
            ++i;
        }else{
            swap(nums[--right], nums[i]);
        }
    }
}

3. 分治 - 快排思想

912.排序数组-快排

思路

  • 解法:快速排序
    在这里插入图片描述
    • 如上图所示,快排本质就是通过一个key值将数组不断的分类排序,当所有子数组(左右区间)排序完毕后,向上返回,完成还原的操作
    • 细节注意:我们使用区间范围内的随机值作为key值,可以避免最坏情况,并均匀分割。

代码

class Solution {
public:
    // 获取随机数
    int getRandom(vector<int>& nums, int left, int right){
        int r = rand();
        return nums[r % (right - left) + left];
    }

    // 快排
    void qsort(vector<int>& nums, int l, int r){
        if(l >= r)  return;

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

    vector<int> sortArray(vector<int>& nums) {
        // 快排 + 三数划分 + 随机数优化
        srand(time(NULL)); // 设置随机数种子
        qsort(nums, 0, nums.size() - 1);
        return nums;
    }
};

215.数组中的第K个最大元素

在这里插入图片描述

4. 分治 - 快速选择

215.数组中的第K个最大元素

思路

我们知道堆排序可以用于解决topk问题,时间复杂度为O(nlogn),这里在引入快速选择算法,一样可以用于解决topK问题,时间复杂度为O(n)

  • 解法:快速选择算法
    在这里插入图片描述
    • 如图所示,依然利用三数划分数组的思想:
    • 我们将数组划分为三部分,求出每一部分的长度
    • 根据k与数组长度关系,找到正确的区间,直到找到正确值

代码

class Solution {
public:
    // 获取随机数
    int getRandom(vector<int>& nums, int left, int right){ 
        return nums[rand() % (right - left + 1) + left];
    }
    
    // 快排
    int qsort(vector<int>& nums, int l, int r, int k){
        if(l == r)  return nums[l];
        
        int left = l - 1, i = l, right = r + 1;
        
        int key = getRandom(nums, l, r);
        while(i < right)
        {
            if(nums[i] < key) swap(nums[++left], nums[i++]);
            else if(nums[i] > key) swap(nums[--right], nums[i]);
            else i++;
        }
            
        // 找第k大的数
        // [l, left] [left + 1, right - 1] [right, r]
        // 区间元素个数: a b c
        // int a = left - l + 1;
        int b = (right - 1) - (left + 1) + 1, c = r - right + 1;
        if(c >= k) return qsort(nums, right, r, k); // 右区间 第k位
        else if(b + c >= k) return key;
        // else if(a >= k) qsort(nums, l, left, k-b-c);
        else return qsort(nums, l, left, k-b-c);
    }
    
    int findKthLargest(vector<int>& nums, int k) {
        // 快速选择算法
        srand(time(NULL));
        return qsort(nums, 0, nums.size() - 1, k);
   }
};

面试题17.14.最小K个数

在这里插入图片描述

思路

  • 题意分析:题目要求设计算法来返回数组中最小的k个数,我们可以使用堆排序,或者快速选择算法
  • 解法:排序 / 堆 / 快速选择
    • 对于解决类似的题,都可以有上述三种做法,但由于上一题题目要求O(n)的时间复杂度,所以选择快速选择算法
    • 这里我们依然以此思想解题
      在这里插入图片描述

代码

class Solution {
public:
    int getRandom(vector<int> &arr, int left, int right){
        return arr[rand() % (right - left + 1) + left];
    }

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

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

        // [l, left] [left+1, right-1] [right, r]
        // 左区间长度: a | 中间区间长度: b
        int a = left - l + 1, b = right - left - 1;
        if(a > k) qsort(arr, l, left, k);
        else if(a + b >= k) return;
        else qsort(arr, right, r, k - a - b);
    }

    vector<int> smallestK(vector<int>& arr, int k) {
        // 三数划分 + 随机数作key + 快速选择
        srand(time(NULL)); // 设置随机数种子
        qsort(arr, 0, arr.size()-1, k);
        return vector<int>(arr.begin(), arr.begin() + k);
    }
};

5. 分治 - 归并思想

912.排序数组_归并

在这里插入图片描述

思路

在这里插入图片描述

在这里插入图片描述

  • 根据上图对比,我们知道归并与快排的区别,但两者都运用了分治的思想
  • 解法:归并
    1. 首先根据mid值递归划分数组
    2. 后向上返回,需要将两有序数组合并:
      • 通过两指针遍历数组,依次比较合并数组
      • 循环结束后将两数组中未合并的数添加
    3. 最后将合并后的数组添加到num中
    • 细节注意:我们使用全局数组tmp,用于节省递归多次创建的时间开胸啊

代码

class Solution {
public:
    vector<int> tmp; // 临时数组 当递归创建多次时,全局遍历节省时间开销

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

        int mid = left + (right - left) / 2;
        // int mid = (left + right) >> 1;
        // 1. 数组划分
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);

        // 2. 合并数组
        int cur1 = left, cur2 = mid + 1, i = 0;
        while(cur1 <= mid && cur2 <= right)
            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
            
        // 2.5 处理未遍历完的数
        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= right) tmp[i++] = nums[cur2++];

        // 3. 将元素写入到nums中
        for(int i = left; i <= right; ++i)
            nums[i] = tmp[i - left];
    }

    vector<int> sortArray(vector<int>& nums) {
        // 归并排序
        tmp.resize(nums.size());
        mergeSort(nums, 0, nums.size() - 1);
        return nums;
    }
};

LCR170.交易逆序对的总数

在这里插入图片描述

思路

  • 解法一:暴力枚举

    • 首先想到的当然是暴力解法,用两层for循环
    • 外层for循环遍历数组每次固定一个数,内层for循环遍历数组寻找比其小的数。
  • 解法二:归并
    在这里插入图片描述

  • 归并

    • 我们有两种策略,即排序时选择1. 升序 2. 降序
      在这里插入图片描述

    在这里插入图片描述

    • 我们选用策略1,即升序排序解题:
      1. 首先根据mid划分数组,递归左右部分并将逆序对个数加到ret中
      2. 对左右部分执行排序操作,当nums[cur1] > nums[cur2] 时,更新ret
      3. 将未合并的元素添加
      4. 最后合并数组

代码

class Solution {
public:
    vector<int> tmp;

    // 归并排序 + 计算逆序对个数
    int mergeSort(vector<int>& nums, int left, int right){
        if(left >= right) return 0; 
        // 划分数组
        int mid = left + (right - left) / 2;
        int ret = 0; // 结果
        ret += mergeSort(nums, left, mid);
        ret += mergeSort(nums, mid + 1, right);

        // 左边部分 排序 右边部分 排序
        int cur1 = left, cur2 = mid + 1, i = 0;
        while(cur1 <= mid && cur2 <= right){
            if(nums[cur1] <= nums[cur2])
                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++];

        // 还原数组
        for(int i = left; i <= right; ++i)
            nums[i] = tmp[i - left];

        return ret;
    }   
    
    int reversePairs(vector<int>& record) {
        tmp.resize(record.size());
        return mergeSort(record, 0, record.size()-1);
    }
};

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

在这里插入图片描述

思路

  • 题意分析:题目要求找到数组nums中 “每一位其右侧小于该位的个数”,且将该个数存放到新数组count中

  • 解法一:暴力枚举

    • 很干脆,两层for循环,前固定数,后遍历从该数到数组末尾的元素,寻找小于自己的个数,统计到count中
  • 解法二:归并
    在这里插入图片描述

    • 根据题意,我们首先创建两个全局数组分别存放临时下标与临时元素,并用index数组保存nums中所有元素下标。
    1. 根据中点划分数组 + 向左右部分递归(找左右部分 满足条件的数)
    2. 通过两指针cur1、cur2遍历数组,进行比较(一左一右)
      • 随后执行上图操作
      • 当cur1元素 > cur2元素,此时cur2后所有元素都是小于自己的,更新结果,并记录cur1元素的下标与值
      • 当cur1元素 <= cur2元素,cur2继续向右移,找符合条件的值

代码

class Solution {
public:
    vector<int> ret; // 结果数组
    vector<int> index; // 记录元素移动前原始下标
    int tmpIndex[100001]; // 临时存放下标
    int tmpNums[100001]; // 临时存放元素

    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;
        while(cur1 <= mid && cur2 <= right){
            if(nums[cur1] <= nums[cur2]){
                tmpNums[i] = nums[cur2];
                tmpIndex[i++] = index[cur2++];
            }else{
                ret[index[cur1]] += right - cur2 + 1;
                tmpNums[i] = nums[cur1];
                tmpIndex[i++] = index[cur1++];
            }
        }
        // 排序剩余元素
        while(cur1 <= mid){
            tmpNums[i] = nums[cur1];
            tmpIndex[i++] = index[cur1++];
        }
        while(cur2 <= right){
            tmpNums[i] = nums[cur2];
            tmpIndex[i++] = index[cur2++];
        }

        // 还原数组
        for(int j = left; j <= right; ++j){
            nums[j] = tmpNums[j-left]; // tmpNums是从0开始的,所以这里还原从0-left
            index[j] = tmpIndex[j-left];
        }
    }

    vector<int> countSmaller(vector<int>& nums) {
        // 哈希思想
        int n = nums.size();
        ret.resize(n);
        index.resize(n);
        // 初始化index数组 保存原始下标
        for(int i = 0; i < n-1; ++i)
            index[i] = i;

        mergeSort(nums, 0, n-1);
        return ret;
    }
};

493.翻转对

在这里插入图片描述

思路

  • 解法一:暴力枚举

    • 两层for循环,外层循环每次固定一位数,内层循环遍历数组判断是否nums[i] > nums[j] *
  • 解法二:归并

    1. 首先关于计算翻转对的操作:
      • 利用单调性,使用同向双指针
    2. 同前面的题一样,这里有两种策略:
      • 策略一:升序
        • 计算在当前元素前,有多少元素的两倍小于自己
      • 策略二:降序
        • 计算在当前元素前,有多少元素的一半大于自己

代码

class Solution {
public:
    vector<int> tmp;

    int mergeSort(vector<int>& nums, int left, int right) {
        if (left >= right) return 0;
        int ret = 0;
        // 先计算左右两侧的翻转对
        int mid = left + (right - left) / 2;
        ret += mergeSort(nums, left, mid);
        ret += mergeSort(nums, mid + 1, right);
        
        // 计算翻转对操作
        int cur1 = left, cur2 = mid + 1;
        while(cur1 <= mid)
        {
            while(cur2 <= right && (nums[cur1] / 2.0 <= nums[cur2])) 
            	cur2++; // 找到符合条件的cur2位置,用*可能溢出
            
            if(cur2 > right) break;
            ret += right - cur2 + 1;
            ++cur1;
        }

        // 具体排序
        // 降序判断
        cur1 = left, cur2 = mid + 1;
        int i = 0;
        while(cur1 <= mid && cur2 <= right)
            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur2++] : nums[cur1++];
        // 排序剩余元素
        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= right) tmp[i++] = nums[cur2++];

        // 还原数组
        for(int j = left; j <= right; ++j)
            nums[j] = tmp[j - left];
        return ret;
    }

    int reversePairs(vector<int>& nums) {
        tmp.resize(nums.size());
        return mergeSort(nums, 0, nums.size() - 1);
    }
};

文章来源:https://blog.csdn.net/Dreaming_TI/article/details/135313018
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。