算法专题七: 分治归并

目录

  • 1. 排序数组
  • 2. 交易逆序对的总数
  • 3. 计算右侧小于当前元素的个数
  • 4. 翻转对

1. 排序数组

在这里插入图片描述
在这里插入图片描述

算法思路: 本道题使用归并的思路进行排序, 先讲数组分为左右两个区间, 然后合并两个有序数组.

class Solution {
    vector<int> tmp;
public:
    vector<int> sortArray(vector<int>& nums) {
        tmp.reserve(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 = (right + left)>>1;
        mergesort(nums,left,mid);
        mergesort(nums,mid+1,right);
        int cur1 = left, cur2 = mid + 1, 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. 交易逆序对的总数

在这里插入图片描述

算法思路:

在这里插入图片描述

先找左半部分的逆序对, 然后再找右半部分的逆序对, 最后再一左一右的找逆序对, 找完左半部分和右半部分之后给数组排个序对数组的结果不影响, 而且排完序之后找一左一右的逆序对还简单些, 不由得我们就可以想到此方法和归并排序的思路一样, 只不过再排序的过程中增加了统计逆序对的个数. 这里可以采用两种策略, 第一种固定当前位置的值, 然后找前面有多少数是比我大的, 第二种策略, 固定当前位置的值, 找后面有多少元素是比我小的.

  • 首先使用第一种策略, 固定一个数, 在前面找比我大的元素的个数.

在这里插入图片描述
当前为升序的排序, 我们归并的时候如果nums[cur1] <= nums[cur2] 时, 此时我们只需要把cur1++就行, 如果nums[cur1]在某一个位置大于nums[cur2]时,此时已经找到了比nums[cur2]大的元素, 那么mid- cur1 + 1这段区间里面的所有值都比nums[cur2]大, 此时统计逆序对的数量即可, 然后再让cur2++, 但是不要往了我们还要排序, 所以这一步写在归并数组那里即可.
那么既然升序可以, 降序可不可以呢?

在这里插入图片描述
如图所示, 该数组为降序的时候, 固定cur1, cur2位置时,如果cur1大于cur2则开始统计cur1中大于cur2元素的个数, 看似没有什么问题, 但是如果进入下一次循环中, cur1++之后还有可能大于cur2,此时在统计那不是重复了嘛, 显然结果是错误的

  • 第二种策略: 固定一个数, 然后找后面比我小的元素的个数

在这里插入图片描述
首先先来看降序的数组, 来统计固定一个位置之后, 后面有多少元素比我小, 当nums[cur1] <= nums[cur2]时, 此时不是我们想要的结果, 我们需要的是nums[cur1]>nums[cur2], 这个时候, 我们统计后面有多少个元素比我小即可, 很显然此时数组是降序的, 所以right - cur2 + 1 即为结果

if(nums[cur1] <= nums[cur2])
tmp[i++] = nums[cur2++];
else
{
ret += right - cur2 + 1;
tmp[i++] = nums[cur1++];
}

反之我们来看一下升序

在这里插入图片描述

此时数组为升序, 我们需要找后面比前面小的元素的个数, 当固定到cur1之后, nums[cur1] > nums[cur2]时, 此时开始找结果, 在后面看在mid到cur2之间的这部分都是比nums[cur1]小的, 但是下一次cur2++之后还有可能是小于nums[cur1]的, 所以此时重复统计了 , 结果是错误的.

代码部分:

策略1

class Solution {
    int tmp[50000];
public:
    int reversePairs(vector<int>& record) {
        return mergeSort(record,0,record.size()-1);
    }
    int mergeSort(vector<int>& nums,int left,int right)
    {
        if(left>=right) return 0;
        int ret = 0;
        int mid = (right + left) >> 1;
        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;
    }
};

策略2

class Solution {
    int tmp[50000];
public:
    int reversePairs(vector<int>& record) {
        return mergeSort(record,0,record.size()-1);
    }
    int mergeSort(vector<int>& nums,int left,int right)
    {
        if(left>=right) return 0;
        int ret = 0;
        int mid = (right + left) >> 1;
        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[cur2++];
            else
            {
                ret += right - cur2 + 1;
                tmp[i++] = nums[cur1++]; 
            }
        }
        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;
    }
};

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

在这里插入图片描述

算法思路:

本道题更上一道题的思路是一模一样的, 上一道题我们采用了策略一的方法, 本道题我们采用策略二, 找后面比当前位置元素小的元素的个数, 但是与上一道题不同的是本道题要求返回对应位置的结果, 这是个问题, 如何解决呢, 我们可以采用哈希的思想, 如果使用哈希表那么如果遇到重复的元素, 我们就无法进行解决, 但是我们可以采用这种思想, 创建一个新的数组, 这个数组中存放的是对应位置原始的下标, 然后这个数组跟着nums一起变化, 但是无论怎样变换, 里面的下标还是最原始的下标位置.

在这里插入图片描述

编写代码:

class Solution {
    vector<int> index;
    vector<int> ret;
    int tmpNums[500010];
    int tmpIndxt[500010];
public:
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        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(left >= right) return;
        int mid = (left + right)>>1;
        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];
                tmpIndxt[i++] = index[cur2++];
            }
            else
            {
                ret[index[cur1]] += right - cur2 + 1;
                tmpNums[i] = nums[cur1];
                tmpIndxt[i++] = index[cur1++];
            }
        }
        while(cur1 <= mid)
        {
            tmpNums[i] = nums[cur1];
            tmpIndxt[i++] = index[cur1++];
        }
        while(cur2 <= right)
        {
            tmpNums[i] = nums[cur2];
            tmpIndxt[i++] = index[cur2++];
        }
        for(int i = left; i <= right; i++)
        {
            nums[i] = tmpNums[i - left];
            index[i] = tmpIndxt[i - left];
        }
    }
};

4. 翻转对

在这里插入图片描述

算法思路:

首先我们还是先考虑两个策略. 策略一, 计算后面有多少个元素的两倍比我小, 策略二. 计算前面有多少元素的一半比我大. 不同于前两题, 本道题无法在归并的时候进行计算, 因为这里的比较逻辑和归并的比较逻辑是不同的, 所以这里我在归并逻辑之前采用双指针的方法先进行统计, 然后在进行归并排序.

在这里插入图片描述

在这里插入图片描述

那么首先来看策略一, 在处理完左右之后并排序之后, 我们处理一左一右的情况, 使用双指针, 计算后面有多少元素的两倍比我小, 如果nums[cur1] <= nums[cur2] * 2, 则说明后面元素的两倍比我大, 那么继续移动cur2, 知道找到cur2的位置两倍比我小, 然后进行统计, 此时cur1++, 进行下一次的统计, 这里cur2还需要回退到mid+1的位置嘛?
答案是不需要的, 因为当前位置cur2位置前面元素的两倍都是比我大的, 那cur1++之后降序, 那么一定也是比我大的, 所以直接统计就可以了, 所以整体的时间复杂度为O(NlogN).

class Solution {
    int tmp[50000];
public:
    int reversePairs(vector<int>& nums) {
        return mergeSort(nums, 0 , nums.size() - 1);
    }
    int mergeSort(vector<int>&nums, int left , int right)
    {
        if(left >= right) return 0;
        int ret = 0;
        int mid = (left + right) >> 1;
        ret += mergeSort(nums,left,mid);
        ret += mergeSort(nums,mid+1,right);
        int cur1 = left, cur2 = mid + 1, i = left;
        while(cur1 <= mid)
        {
            while(cur2 <= right && nums[cur2] >= nums[cur1] / 2.0) cur2++;
            if(cur2 > right) break;//小优化
            ret += right - cur2 + 1;
            cur1++;
        }
        //降序
        cur1 = left, cur2 = mid + 1;
        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 j = left; j <= right; j++)
            nums[j] = tmp[j]; 
        return ret;
    }
};

策略二: 找前面有多少元素的一半比我大

在这里插入图片描述

其实更策略一的逻辑是类似的, 只不过这里的数组是升序排列的, 找前面有多少元素的一半比我大, 先让cur1走, 如果/2之后大于nums[cur2]则, cur1++, 找到位置之后统计ret, 然后让cur2++,进行下一次的统计, 此时cur1也不需要回去, cur1之前的位置一半都是比cur2小的, 那么cur2++之后一定还是比cur1小, 所以cur2直接++即可.

class Solution {
    int tmp[50000];
public:
    int reversePairs(vector<int>& nums) {
        return mergeSort(nums, 0, nums.size()-1);
    }
    int mergeSort(vector<int>& nums,int left, int right)
    {
        if(left >= right) return 0;
        int mid = (left + right) >> 1;
        int ret = 0;
        ret += mergeSort(nums,left,mid);
        ret += mergeSort(nums,mid+1,right);
        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;
        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 j = left ; j <= right ; j++)
            nums[j] = tmp[j];
        return ret;
    }
};

完

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

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

相关文章

[含文档+PPT+源码等]精品基于php实现的原生微信小程序心理健康服务系统的设计与实现

[含文档+PPT+源码等]精品基于php实现的原生微信小程序心理健康服务系统的设计与实现

基于PHP实现的原生微信小程序心理健康服务系统的设计与实现背景&#xff0c;可以从以下几个方面进行详细阐述&#xff1a; 一、技术背景 PHP技术&#xff1a; 广泛应用&#xff1a;PHP是一种开源的服务器端脚本语言&#xff0c;广泛用于Web开发领域。其丰富的函数库和灵活的语…
阅读更多...
Redis-04 主从架构原理与搭建及主从优化方案

Redis-04 主从架构原理与搭建及主从优化方案

生产中使用Redis往往非单机部署&#xff0c;虽然根据前文已经对redis做了数据持久化处理&#xff0c;但是如果Redis服务宕机&#xff0c;所有的数据操作都将直接进入数据库&#xff0c;如果操作量很大&#xff0c;则相当于出现缓存穿透的现象。故生产中使用Redis一般采取【主从…
阅读更多...
鸿蒙系统开发快速入门教程

鸿蒙系统开发快速入门教程

一、开发环境准备 1. 下载并安装DevEco Studio DevEco Studio是华为官方提供的鸿蒙应用开发IDE&#xff0c;集成了开发、调试、模拟运行等功能&#xff0c;是鸿蒙开发的首要工具。 下载地址&#xff1a;前往华为开发者官网下载DevEco Studio。安装步骤&#xff1a;按照官方提…
阅读更多...
类文件结构

类文件结构

文章目录 类文件结构字节码Class 文件结构总结魔数&#xff08;Magic Number&#xff09;Class 文件版本号&#xff08;Minor&Major Version&#xff09;常量池&#xff08;Constant Pool&#xff09;访问标志(Access Flags)当前类&#xff08;This Class&#xff09;、父类…
阅读更多...
Luminar Neo v1.21.0.13934 图像编辑软件绿色便携版

Luminar Neo v1.21.0.13934 图像编辑软件绿色便携版

skylum Luminar Neo 是一款由未来 AI 技术驱动的创意图像编辑器。并且支持微软Windows及苹果Mac OX系统&#xff0c;它使创作者能够将他们最大胆的想法变为现实并乐在其中。借助 Luminar Neo 领先的 AI 技术和灵活的工作流程&#xff0c;完成创意任务并获得专业品质的编辑结果。…
阅读更多...
Python_函数式编程（内存管理机制）

Python_函数式编程（内存管理机制）

将压缩文件减压&#xff0c;可以看到有很多文件&#xff0c;主要关心两个&#xff08;Include、Objects&#xff09;在Include目录下object.h中可以查看创建对象的结构体。 在创建对象时&#xff0c;每个对象至少内部4个值&#xff0c;PyObject结构体(上一个对象、下一个对象、…
阅读更多...
Docker-Consul概述以及集群环境搭建

Docker-Consul概述以及集群环境搭建

文章目录 一、Docker consul概述二、consul 部署1.consul服务器2.registrator服务器&#xff08;客户端&#xff09;2.consul-template&#xff08;在consul服务器&#xff09;3.consul 多节点 一、Docker consul概述 容器服务更新与发现&#xff1a;先发现再更新&#xff0c;…
阅读更多...
51单片机快速入门之 LED点阵 结合74hc595 的应用 2024/10/16

51单片机快速入门之 LED点阵 结合74hc595 的应用 2024/10/16

51单片机快速入门之 LED点阵 结合74hc595 的应用 74HC595是一种常用的数字电路芯片&#xff0c;具有串行输入并行输出的功能。它主要由两个部分组成&#xff1a;一个8位的移位寄存器和一个8位的存储寄存器。数据通过串行输入管脚&#xff08;DS&#xff09;逐位输入&#xff0…
阅读更多...
再Android10上实现检测AHD摄像头是否接入

再Android10上实现检测AHD摄像头是否接入

项目有个需要&#xff0c;需要知道tp9951是否接入AHD摄像头 1&#xff0c;驱动层可以通过读取寄存器的值来检测是否接入AHD摄像头 tp9951_write_reg(0x40, 0x00); //select decoder page tp9951_write_reg(0x41, ch); val tp9951_read_reg(TP_INPUT_STATUS_REG);…
阅读更多...
通过华为鲲鹏认证的软件产品如何助力信创产业

通过华为鲲鹏认证的软件产品如何助力信创产业

软件通过华为鲲鹏认证与信创产业有着密切的联系。鲲鹏认证是华为推动信创产业发展的一项重要举措&#xff0c;通过该认证&#xff0c;软件可以在华为的生态系统中实现更好的兼容性和性能优化&#xff0c;从而推动信创产业的全面发展和国产化替代。 鲲鹏认证的定义和重要性 鲲鹏…
阅读更多...
python基于大数据的电影市场预测分析

python基于大数据的电影市场预测分析

一、摘要 智慧是改变生活和生产的一种来源&#xff0c;那么智慧的体现更大程度上是对于软件技术的改变。当今社会&#xff0c;好的思路&#xff0c;好的创新方式往往是改变人们生活的一种来源。最常见最直接的形式就是各种软件的创始思路&#xff0c;京东因为非典的流行才能够…
阅读更多...
[全国/全省/全市]初赛知识点复习大汇总

[全国/全省/全市]初赛知识点复习大汇总

目录 计算机结构与组成原理 计算机发展及应用 1、第一台电子计算机的诞生&#xff1a; ENIAC 2、第一台具有存储程序功能的计算机&#xff1a;EDVAC。 图灵 计算机发展阶段 世界上最快的超级计算机 计算机应用 计算机保护知识产权 计算机病毒 硬件系统的组成 概述 …
阅读更多...
分享一个图片RGB以及16进制颜色提取的在线网站

分享一个图片RGB以及16进制颜色提取的在线网站

IMAGECOLORPICKER.com 网站链接:传送门呢 可以在线上传自己的图片,然后识别图片的颜色,比较方便。
阅读更多...
2024年第九届数维杯大学生数学建模挑战赛赛题和数维杯国际数学建模 LaTeX 模板

2024年第九届数维杯大学生数学建模挑战赛赛题和数维杯国际数学建模 LaTeX 模板

2024年数维杯国际大学生数学建模挑战赛参赛规则 数维杯大学生数学建模竞赛每年分为两场&#xff0c;每年上半年为数维杯全国赛(5月下旬) &#xff0c;下半年为数维杯国际挑战赛(11月下旬)&#xff0c;已连续成功举办九届&#xff0c;2023年数维杯国际大学生数学建模挑战赛共有近…
阅读更多...
【论文阅读】DL-SRIR综述2023

【论文阅读】DL-SRIR综述2023

0. 摘要 SISR与DL的介绍 单图像超分辨率(SISR)是计算机视觉的一个重要研究领域,其目的是从低分辨率(LR)图像中恢复清晰、高分辨率(HR)图像。 随着深度学习理论和技术的快速发展,深度学习被引入到图像超分辨率(SR)领域,并在许多领域取得了远远超过传统方法的成果。 本文框架…
阅读更多...
Mapbox GL 加载GeoServer底图服务器的WMS source

Mapbox GL 加载GeoServer底图服务器的WMS source

貌似加载有点慢啊&#xff01;&#xff01; 1 这是底图 2 这是加载geoserver中的地图效果 3源码 3.1 geoserver中的网络请求 http://192.168.10.10:8080/geoserver/ne/wms?SERVICEWMS&VERSION1.1.1&REQUESTGetMap&formatimage/png&TRANSPARENTtrue&STYL…
阅读更多...
ImportError: /../lib/libstdc++.so.6: version `GLIBCXX_3.4.29解决方案

ImportError: /../lib/libstdc++.so.6: version `GLIBCXX_3.4.29解决方案

今天跑实验遇到了一个头疼的报错&#xff0c;完全看不懂&#xff0c;上网查了一下成功解决&#xff0c;但是网上的指令没法直接拿来用&#xff0c;所以在这里记录一下自己的解决方案。 报错信息&#xff1a; Traceback (most recent call last):File "/home/shizhiyuan/c…
阅读更多...
数据结构 —— 树和二叉树简介

数据结构 —— 树和二叉树简介

目录 0.前言 1.树的认识 什么是树 树的相关概念 树的表示 孩子兄弟表示法 2.二叉树的认识 什么是二叉树 特殊的二叉树 满二叉树 完全二叉树 二叉树的性质 性质一 性质二 性质三 二叉树的存储 顺序存储 链式存储 0.前言 笔者我之前讲解的数据结构都是线性…
阅读更多...
OceanBase 的写盘与传统数据库有什么不同？

OceanBase 的写盘与传统数据库有什么不同？

背景 在数据库开发过程中&#xff0c;“写盘”是一项核心操作&#xff0c;即将内存中暂存的数据安全地转储到磁盘上。在诸如MySQL这样的传统数据库管理系统中&#xff0c;写盘主要有以下几步&#xff1a;首先将数据写入缓存池&#xff1b;其次&#xff0c;为了确保数据的完整性…
阅读更多...
深入理解Qt中的QTableView、Model与Delegate机制

深入理解Qt中的QTableView、Model与Delegate机制

文章目录 显示效果QTableViewModel(模型)Delegate(委托)ITEM控件主函数调用项目下载在Qt中，视图(View)、模型(Model)和委托(Delegate)机制是一种非常强大的架构，它们实现了MVC(模型-视图-控制器)设计模式。这种架构分离了数据存储(模型)、数据展示(视图)和数据操作(委托)，使…
阅读更多...
最新文章

Copyright @ 2022~2023