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

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);
    }
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/287466.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

企业如何利用好数据，让数据真正成为数据资产？数据资产管理应该怎样建设？

企业如何利用好数据，让数据真正成为数据资产？数据资产管理应该怎样建设？

数字化时代&#xff0c;数据已经成为了个人、机构、企业乃至国家的重要战略资产。 近日&#xff0c;财政部正式对外发布《企业数据资源相关会计处理暂行规定》&#xff0c;并自 2024 年 1 月 1 日开始施行。数据资产入表政策落地节奏超预期&#xff0c;标志着国家把数据作为生…
阅读更多...
如何用python实时监控股票，并且持续扫描大盘？

如何用python实时监控股票，并且持续扫描大盘？

用 Python 抓取分析股市数据很简单&#xff01;只用短短几行代码&#xff0c;就能实现策略制定到交易信号生成。 一、数据准备 在分析的最开始&#xff0c;需要获取数据。本文中将以沪深 300 指数为标的进行分析&#xff08;包含日期、开高低收价、成交量、成交额字段&#xf…
阅读更多...
MySQL之四大引擎、账号管理以及建库认识

MySQL之四大引擎、账号管理以及建库认识

目录 一、数据库存储引擎&#xff08;发动机&#xff09; 1.1、认识引擎 1.2、查看存储引擎 1.3、引擎常识 1.4、support字段说明 1.5、四大引擎 二、数据库管理 2.1、元数据库介绍&#xff1a; 2.2、分类&#xff1a; 2.3、增删改查以及使用操作 2.4、权限 三、数…
阅读更多...
【面试高频算法解析】算法练习2 回溯

【面试高频算法解析】算法练习2 回溯

目录 前言算法解析练习题组合总和全排列II单词搜索 前言 本篇章开放目的是按算法类型学习算法&#xff0c;学习对应算法理论&#xff0c;并通过练习一些经典算法题深入理解这类算法&#xff0c;避免出现刷了很多算法题&#xff0c;还是一知半解的状态 算法解析 回溯&#xff…
阅读更多...
UDP通信（服务器-客户端）

UDP通信（服务器-客户端）

一、 UDP服务器-客户端通信 UDP&#xff08;User Datagram Protocol&#xff09;是一种面向无连接的传输层协议&#xff0c;它提供了一种简单的、不可靠的数据传输服务。与TCP&#xff08;Transmission Control Protocol&#xff09;不同&#xff0c;UDP不建立连接&#xff0c;…
阅读更多...
FusionAccess配置Lite AD

FusionAccess配置Lite AD

1、Lite AD的安装及配置 Lite AD流程&#xff1a; &#xff08;1&#xff09;创建一个新的Windows 10&#xff0c;安装tools&#xff0c;再安装ITA组件&#xff08;安装Lite AD会自动安装VAG/VLB&#xff09; &#xff08;2&#xff09;创建一个新的Windows 10&#xff0c;安…
阅读更多...
线性规划中解的关系

线性规划中解的关系

写于&#xff1a;2024年1月2日星期二 修改于&#xff1a; 本文从两个角度对线性规划中的解做划分&#xff0c;角度一是将解划为基解、基可行解、可行解&#xff1b;角度二是将解划分为无可行解、无界解、最优解&#xff08;唯一和无穷多&#xff09;。同时&#xff0c;详细描述…
阅读更多...
【计算机视觉网络训练技巧】你知道你拿什么图片在训练吗？训练图片可视化简易版

【计算机视觉网络训练技巧】你知道你拿什么图片在训练吗？训练图片可视化简易版

以下是一张图片&#xff0c;数据增广之后的示意图&#xff1a; 问题是这样的&#xff0c;当数据增广后&#xff0c;我们怎么知道图片变成什么样了呢&#xff0c;或者说我们输入到网络中的图片长什么样&#xff1f;对&#xff0c;解法很简单&#xff0c;就是在图片输入到网络时…
阅读更多...
C++的基础语句

C++的基础语句

C前奏 1.变量的定义2.键入和输出3.运算符4.sizeof()函数5.判断6.goto语句7.总结 这个专题&#xff0c;我会用简单的语言介绍C的语法&#xff0c;并会适当的对比实现相同或相似功能的C与python代码写法上的不同。 1.变量的定义 对于python来说&#xff0c;我们可以跳过定义直接…
阅读更多...
Efficient Classification of Very Large Images with Tiny Objects（CVPR2022补1）

Efficient Classification of Very Large Images with Tiny Objects（CVPR2022补1）

文章目录 Two-stage Hierarchical Attention SamplingsummaryOne-stageTwo-Stage内存需求 Efficient Contrastive Learning with Attention Sampling Two-stage Hierarchical Attention Sampling summary 从一个大图像中按照指定的低分辨率比例和位置提取出一个小图块 一阶段…
阅读更多...
web前端——clear可以清除浮动产生的影响

web前端——clear可以清除浮动产生的影响

clear可以解决高度塌陷的问题&#xff0c;产生的副作用要小 未使用clear之前 <!DOCTYPE html> <head><meta charset"UTF-8"><title>高度塌陷相关学习</title><style>div{font-size:50px;}.box1{width:200px;height:200px;backg…
阅读更多...
阿里云盘在线自动签到-无需部署

阿里云盘在线自动签到-无需部署

声明&#xff1a;本文的代码内容来源于知乎用户小猪猪和艾欧娜传播此内容是基于学术研究和学习目的&#xff0c;遵循了适用的版权规定和学术研究的合理使用原则。 作者只对源代码进行了一点点改动&#xff0c;本文主要演示如何使用金山文档的每日定时任务&#xff0c;执行阿里云…
阅读更多...
nccl 源码安装与应用示例 附源码

nccl 源码安装与应用示例 附源码

1&#xff0c; 官方下载网址 注意&#xff0c;本文并不使用nv预编译的包来安装&#xff0c;仅供参考&#xff1a; NVIDIA Collective Communications Library (NCCL) | NVIDIA Developer 2&#xff0c;github网址 这里是nv开源的nccl源代码&#xff0c;功能完整&#xff0c;不…
阅读更多...
Adobe Experience Design安装指南

Adobe Experience Design安装指南

XD&#xff08;Adobe Experience Design&#xff09;下载链接 https://pan.baidu.com/s/1MVcaE2GB1Q9YpgmgDxUGJw?pwd0531 1.鼠标右击【Adobe XD 55.1(64bit)】压缩包选择&#xff08;win11以上系统需先点击“显示更多选项”&#xff09;【解压到 Adobe XD 55.1(64bit)】。 …
阅读更多...
《JVM由浅入深学习【四】 2023-12-24》JVM由简入深学习提升分享

《JVM由浅入深学习【四】 2023-12-24》JVM由简入深学习提升分享

JVM由简入深学习提升分享四 1.JVM中java堆的特点及作用2. JVM中对象如何在堆内存中分配3. JVM堆内存中的对象布局 1.JVM中java堆的特点及作用 是线程共享的一块区域虚拟机启动时就创建了是虚拟机中内存占用很大的一块存放所有的实例对象和数组GC主要的作用区域可分为新生代&am…
阅读更多...
关于“Python”的核心知识点整理大全50

关于“Python”的核心知识点整理大全50

目录 python_repos.py 17.1.6 概述最受欢迎的仓库 python_repos.py 17.1.7 监视 API 的速率限制 注意 17.2 使用 Pygal 可视化仓库 python_repos.py 17.2.1 改进 Pygal 图表 python_repos.py 往期快速传送门&#x1f446;&#xff08;在文章最后&#xff09;&#xf…
阅读更多...
09、docker 安装nacos并配置mysql存储配置信息

09、docker 安装nacos并配置mysql存储配置信息

docker 安装nacos并配置mysql存储配置信息 1、docker启动nacos的各种方式2、Docker安装nacos3、MySQL中新建nacos的数据库4、挂载数据or配置目录5、运行 1、docker启动nacos的各种方式 内嵌derby数据源 docker run -d \ -e PREFER_HOST_MODEhostname \ -e SPRING_DATASOURCE_…
阅读更多...
python旅游大数据分析可视化大屏 游客分析+商家分析+舆情分析 计算机毕业设计（附源码）Flask框架✅

python旅游大数据分析可视化大屏 游客分析+商家分析+舆情分析 计算机毕业设计（附源码）Flask框架✅

毕业设计&#xff1a;2023-2024年计算机专业毕业设计选题汇总&#xff08;建议收藏&#xff09; 毕业设计&#xff1a;2023-2024年最新最全计算机专业毕设选题推荐汇总 &#x1f345;感兴趣的可以先收藏起来&#xff0c;点赞、关注不迷路&#xff0c;大家在毕设选题&#xff…
阅读更多...
详解静态网页数据获取以及浏览器数据和网络数据交互流程-Python

详解静态网页数据获取以及浏览器数据和网络数据交互流程-Python

目录 前言 一、静态网页数据 二、网址通讯流程 1.DNS查询 2.建立连接 3.发送HTTP请求 4.服务器处理请求 5.服务器响应 6.渲染页面 7.页面交互 三、URL/POST/GET 1.URL 2.GET 形式 3.POST 形式 四.获取静态网页数据 1.requests库 点关注&#xff0c;防走丢&am…
阅读更多...
Linux vi/vim 教程

Linux vi/vim 教程

文章目录 【 1. vi/vim 的三种模式 】1.1 命令模式1.2 输入模式1.3 底线命令模式 【 2. 实例 】【 3. vim 的其他命令 】 所有的 Unix Like 系统都会内建 vi 文本编辑器&#xff0c;其他的文本编辑器则不一定会存在。目前我们使用比较多的是 vim 编辑器。vim 从 vi 发展出来&am…
阅读更多...
最新文章

Copyright @ 2022~2023