leetcode算法之分治-归并

目录

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

1.排序数组

排序数组
在这里插入图片描述

//分治-归并
class Solution {
    int tmp[50010];
public:
    vector<int> sortArray(vector<int>& nums) {
        mergeSort(nums,0,nums.size()-1);
        return nums;
    }

    void mergeSort(vector<int>& nums,int left,int right)
    {
        if(left>=right) return;
        //1.选择中间点划分区间
        int mid = (left+right)>>1;
        //[left,mid][mid+1,right]
        //2.将左右两区间排序
        mergeSort(nums,left,mid);
        mergeSort(nums,mid+1,right);
        //3.合并两个有序数组
        int cur1 = left,cur2 = mid+1,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];
        }
    }
};

2.数组中的逆序对

数组中的逆序对
在这里插入图片描述

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)
    {
        if(left>=right) return 0;
        int ret = 0;
        //1.选择中间元素划分区间
        int mid = (left+right)>>1;
        //[left,mid][mid+1,right]
        //2.计算左右区间的逆序对的个数
        ret += mergeSort(nums,left,mid);
        ret += mergeSort(nums,mid+1,right);
        //3.计算一左一右逆序对的个数+合并两个有序数组
        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 j=left;j<=right;j++)
        {
            nums[j] = tmp[j-left];
        }

        return ret;
    }
};

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

计算右侧小于当前元素的个数
在这里插入图片描述

class Solution {
    vector<int> ret;
    vector<int> index;//记录nums当前元素的原始下标

    int tmpNums[500010];
    int tmpIndex[500010];
public:
    vector<int> countSmaller(vector<int>& nums) {
        //计算当前元素之后,有多少个比我小(降序)
        int n = nums.size();
        ret.resize(n);
        index.resize(n);
        //初始化index数组
        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;
        //1.选择中间元素划分区间
        int mid = (left+right)>>1;
        //[left,mid][mid+1,right]
        //2.将左右区间进行排序
        mergeSort(nums,left,mid);
        mergeSort(nums,mid+1,right);
        //3.处理一左一右的情况
        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];
            index[j] = tmpIndex[j-left];
        }
    }
};

4.翻转对

翻转对
在这里插入图片描述

//计算当前元素之前,有多少元素的一半比我大--升序
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)
    {
        if(left>=right) return 0;
        int ret = 0;
        //1.选择中间元素划分区间
        int mid = (left+right)>>1;
        //[left,mid][mid+1,right]
        //2.计算左右区间翻转对的个数
        ret += mergeSort(nums,left,mid);
        ret += mergeSort(nums,mid+1,right);
        //3.先计算翻转对的个数
        int cur1 = left,cur2 = mid+1,i=0;
        while(cur2<=right)//升序的情况
        {
            while(cur1<=mid && nums[cur1]/2.0<=nums[cur2]) cur1++;
            if(cur1 > mid) 
                break;
            ret += mid-cur1+1;
            cur2++;
        }
        //4.合并两个有序数组
        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-left];
        }
        return ret;
    }
};
//计算当前元素后面,有多少元素的两倍比我小--降序
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)
    {
        if(left>=right) return 0;
        int ret = 0;
        //1.选择中间元素划分区间
        int mid = (left+right)>>1;
        //[left,mid][mid+1,right]
        //2.计算左右区间翻转对的个数
        ret += mergeSort(nums,left,mid);
        ret += mergeSort(nums,mid+1,right);
        //3.先计算翻转对的个数
        int cur1 = left,cur2 = mid+1,i=0;
        while(cur1<=mid)//降序的情况
        {
            while(cur2<=right && nums[cur1]/2.0<=nums[cur2]) cur2++;
            if(cur2 > right) 
                break;
            ret +=right-cur2+1;
            cur1++;
        }
        //4.合并两个有序数组
        cur1 = left,cur2 = mid+1;
        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;
    }
};

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

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

相关文章

线程池简介及其简单实现

如果需要频繁的创建销毁线程, 就需要想办法降低创建和销毁的开销, 而线程池就是一个很好的选择: 提前创建好一些线程, 等到需要使用线程的时候, 直接从池子里拿一个就好了, 当不再使用该线程时, 就放回到池子里. 那么此时就从 创建/销毁线程 -> 池子里取线程/将线程还到池子…

找不到vcruntime140_1.dll,无法继续执行代码怎么办?5个可以解决的方案分享

在计算机使用过程中&#xff0c;我们经常会遇到一些错误提示&#xff0c;其中之一就是“VCRuntime140_1.dll缺失”。这个错误通常会导致某些应用程序无法正常运行。为了解决这个问题&#xff0c;我们需要进行修复操作。本文将介绍5个修复VCRuntime140_1.dll缺失的方法&#xff…

解锁电力安全密码:迅软DSE助您保护机密无忧

电力行业信息化水平不断提高&#xff0c;明显提升了电力企业的生产运营能力&#xff0c;然而随着越来越多重要信息存储在终端计算机中&#xff0c;电力面临的信息安全挑战也越来越多。 作为关键基础设施的基础&#xff0c;电力企业各部门产生的资料文档涵盖着大量机密信息&…

微信小程序 prettier 格式化

一、安装prettier插件 二、打开设置 然后再打开setting.json 新增代码 {"editor.formatOnSave": true,"editor.defaultFormatter": "esbenp.prettier-vscode","prettier.documentSelectors": ["**/*.wxml", "**/*.wx…

基于AVR单片机的移动目标视觉追踪系统设计与实现

基于AVR单片机的移动目标视觉追踪系统是一种常见的应用领域&#xff0c;旨在通过摄像头采集图像数据并使用图像处理和追踪算法实现对移动目标的实时追踪。本文将介绍基于AVR单片机的移动目标视觉追踪系统的设计原理和实现步骤&#xff0c;并提供相应的代码示例。 1. 设计概述 …

革新突破!智能指标平台引领时代,国产大模型与企业级部署的完美结合

11月21日&#xff0c;跬智信息&#xff08;Kyligence&#xff09;圆满召开了线上数智论坛暨产品发布会&#xff0c;升级智能一站式指标平台 Kyligence Zen 及 AI 数智助理 Kyligence Copilot 的一系列企业级能力&#xff0c;包括正式支持智谱 AI、百川智能等在内的多款国产大模…

SVN创建分支

一 从本地创建方式可指定版本号进行分支创建。 1、在本地目录右击 -----> 点击branch/tag(分支/标签) From: 源&#xff0c;可指定具体的版本号&#xff0c; To path: 可通过"..."选择分支路径 最后点击确定&#xff0c;交由服务器执行创建。 二 通过SVN客…

List操作的一些常见问题

文章目录 阿里巴巴开发手册强制规约&#xff1a;1. Arrays.asList转换基本类型数组2. Arrays.asList返回的List不支持增删操作3. 对原始数组的修改会影响到我们获得的那个List4. ArrayList.subList强转ArrayList导致异常5. ArrayList中的subList切片造成OOM6.Copy-On-Write 是什…

上海亚商投顾:北证50指数大涨 机器人概念股掀涨停潮

上海亚商投顾前言&#xff1a;无惧大盘涨跌&#xff0c;解密龙虎榜资金&#xff0c;跟踪一线游资和机构资金动向&#xff0c;识别短期热点和强势个股。 一.市场情绪 三大指数昨日震荡反弹&#xff0c;黄白二线有所分化&#xff0c;题材热点轮动表现。北证50指数大涨超3%&#…

「MACOS限定」 如何将文件上传到GitHub仓库

介绍 本期讲解&#xff1a;如何在苹果电脑上上传文件到github远程仓库 注&#xff1a;写的很详细 方便我的朋友可以看懂操作步骤 第一步 在电脑上创建一个新目录&#xff08;文件夹&#xff09; 注&#xff1a;创建GitHub账号、新建github仓库、git下载的步骤这里就不过多赘…

股票统计信息(七)

7-统计信息 文章目录 7-统计信息一. 股票周级别统计信息二. 查询可支持的所有的股票资金类型三. 股票图形统计信息四. 查询当前用户自选表里面最近十天的交易信息五. 查看天/星期范围统计的历史记录六. 查看最近多少天某个属性的涨跌幅度值 一. 股票周级别统计信息 接口描述: …

使用Python处理ADC激光测距数据并绘制为图片(二)

使用Python处理ADC激光测距数据并绘制为图片 说明一、定义全局变量变二、保存和清空原始数据三、拆分原始数据为键值对四、获取标题、FigText、更新统计信息文件五、生成图片六、处理原始数据文件七、主函数入口八、测试结果 说明 1. 主要是将ADC激光测距叠加后的1024Byte数据绘…

【码神之路】【Golang】博客网站的搭建【学习笔记整理 持续更新...】

介绍 一个用原生GO开发的博客网站&#xff0c;涉及Golang Web开发、Web服务器搭建和HTTP请求处理、模板与静态资源处理等 技术栈 后端&#xff1a;Go、Go并发机制前端&#xff1a;HTML模版链接直达 Golang搭建博客网站的学习视频 注&#xff1a;这里我只记录我实质✅学习到…

PyCharm玩转ESP32

想必玩ESP32的童鞋都知道Thonny&#xff0c;当然学Python的童鞋用的更多的可能是PyCharm和VsCode Thonny和PyCharm的对比 对于PyCharm和VsCode今天不做比较&#xff0c;今天重点说一下用PyCharm玩转ESP32&#xff0c;在这之前我们先对比下Thonny和PyCharm的优缺点 1、使用Tho…

引迈-JNPF低代码项目技术栈介绍

从 2014 开始研发低代码前端渲染&#xff0c;到 2018 年开始研发后端低代码数据模型&#xff0c;发布了JNPF开发平台。 谨以此文针对 JNPF-JAVA-Cloud微服务 进行相关技术栈展示&#xff1a; 1. 项目前后端分离 前端采用Vue.js&#xff0c;这是一种流行的前端JavaScript框架&a…

webpack 配置

1、基础配置 // node js核心模塊 const path require(path) // 插件是需要引入使用的 const ESLintPlugin require(eslint-webpack-plugin) // 自动生成index.html const HtmlWebpackPlugin require(html-webpack-plugin); // 将css文件单独打包&#xff0c;在index.html中…

【开源】基于Vue.js的教学过程管理系统

项目编号&#xff1a; S 054 &#xff0c;文末获取源码。 \color{red}{项目编号&#xff1a;S054&#xff0c;文末获取源码。} 项目编号&#xff1a;S054&#xff0c;文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 教师端2.2 学生端2.3 微信小程序端2…

iOS越狱检测总结

文章目录 前言检测越狱文件私有目录检测检测越狱软件检测系统目录是否变为链接动态库检测环境变量检测系统调用检测指令集调用检测其他方式检测 前言 在之前的文章中&#xff0c;已经带大家一起制作了一个屏蔽越狱检测的Tweak。本文就和大家一起学习整理一下iOS系统中有哪些越…

scala的schema函数(算子)

在翻阅一些代码的时候&#xff0c;schema算子好像没碰到过&#xff0c;比较好奇structField这个类型&#xff0c;为什么可以直接用name参数&#xff0c;就翻阅了下资料&#xff1a; 在 Apache Spark 中&#xff0c;DataFrame 是一种分布式的数据集&#xff0c;它是以类似于关系…

电脑便签功能在哪里找?电脑桌面便签怎么添加?

很多上班族在使用电脑办公的时候&#xff0c;都需要随手记录工作事项&#xff0c;例如记录共同工作时的想法、会议笔记、常用工作资料、每天待办的工作任务等事项&#xff0c;这时候使用纸质的笔记本来记录工作&#xff0c;不仅不方便随时查看和使用&#xff0c;而且在修改、删…