leetcode 困难 —— 数组中的逆序对(分治法)
题目:
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。
题解:
① 我最开始想的蠢方法(会超时,可跳过)
首先题目求的逆序对,这考虑的关键应该就是 位置 和 大小
那么我们先将大小排个序,然后从小到大考虑
然后我们按数字从小到大放到由位置排序的容器中
每一次放入,二分搜索当前要放入值的位置,其之后的值的数量,就是该值组成的逆序对数量
这样是不是可以只用考虑位置(因为之前放入容器的值的大小都小于当前值)
这样排序 O(nlogn),然后每次放入值前二分搜索 O(nlogn),但是还是超时了
应该是那个 insert 复杂度太高了,没办法,vector 的 insert 复杂度为 O(n)
想过用其他容器,但好像都不能解决,要是大佬有方法,欢迎评论私信,真想不出来 😟
代码如下:
class Solution {
public:vector<pair<int, int> > temp1;vector<pair<int, int> > temp2;int reversePairs(vector<int>& nums) {int res = 0;for(int i = 0; i < nums.size(); i++) {temp1.push_back(make_pair(nums[i], i));}sort(temp1.begin(), temp1.end());for(int i = 0; i < temp1.size(); i++) {pair<int, int> t = make_pair(temp1[i].second, temp1[i].first);int f = lower_bound(temp2.begin(), temp2.end(), t) - temp2.begin();res = res + i - f;temp2.insert(temp2.begin() + f, t);}return res;}
};
② 分治法(害,我这笨脑子,真的想不到啊)
分治排序都知道吧
我们在排序的过程中,考虑逆序对数量
首先两个有序的序列,求逆序对数量
左边的序列中的某个值所组成逆序对等于右边所有小于它的值的数量
可以通过分治法求解的原理,即
局部的排序,不会影响这部分和其他部分组成逆序对
代码如下:
class Solution {
public:vector<int> numbers;int res = 0;void solve(int l, int r) {int mid = (r + l) / 2;if(r - l > 1) {solve(l, mid);solve(mid, r);}else {return;}vector<int> temp;int flag1 = l, flag2 = mid;while(flag1 < mid) {while(flag2 < r && numbers[flag1] > numbers[flag2]) {temp.push_back(numbers[flag2]);flag2++;}temp.push_back(numbers[flag1]);flag1++;res = res + flag2 - mid;}while(flag2 < r) {temp.push_back(numbers[flag2]);flag2++;}for(int i = l; i < r; i++) {numbers[i] = temp[i - l];}}int reversePairs(vector<int>& nums) {numbers = nums;solve(0, nums.size());return res;}
};
相关文章:
leetcode 困难 —— 数组中的逆序对(分治法)
题目: 在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。 题解: ① 我最开始想的蠢方法(会超时,可跳过ÿ…...
02.24:图片的风格转换
Github网址:https://github.com/lengstrom/fast-style-transfer 在anaconda prompt中切换环境命令:activate 环境名 列出所有环境名:conda info --envs 安装环境:conda create -n 环境名 pythonx.x.x 删除某环境:co…...
[SSD综述 1.3] SSD及固态存储技术半个世纪发展史
在我们今天看来,SSD已不再是个新鲜事物。这多亏了存储行业的前辈们却摸爬滚打了将近半个世纪,才有了SSD的繁荣, 可惜很多前辈都没有机会看到。所有重大的技术革新都是这样,需要长期的技术积累,一代一代的工程师们默默的…...
PAT 1023 组个最小数(分数20)题目有bug
目录 题目描述: 题目讲解: 框架构建: 代码部分: 一个bug: 题目描述: 给定数字 0-9 各若干个。你可以以任意顺序排列这些数字,但必须全部使用。目标是使得最后得到的数尽可能小(…...
QML 中的 5 大布局
作者: 一去、二三里 个人微信号: iwaleon 微信公众号: 高效程序员 在 QML 中,可以通过多种方式对元素进行布局 - 手动定位、坐标绑定定位、锚定位(anchors)、定位器和布局管理器。 说到 anchors,可能很多人都不太了解,它是 QML 中一个非常重要的概念,主要提供了一种相…...
使用Python进行数据分析——线性回归分析
大家好,线性回归是确定两种或两种以上变量之间互相依赖的定量关系的一种统计分析方法。根据自变量的个数,可以将线性回归分为一元线性回归和多元线性回归分析。一元线性回归:就是只包含一个自变量,且该自变量与因变量之间的关系是…...
我眼中的柔宇科技
关注、星标公众号,直达精彩内容来源:技术让梦想更伟大作者:李肖遥很早就知道了柔宇科技,当时是因为知道创始人刘自鸿,23岁清华本硕毕业,26岁获斯坦福大学电子工程博士学位,历时不超过3年&#x…...
Allegro如何快速把视图居中显示操作指导
Allegro如何快速把视图居中显示操作指导 用Allegro进行PCB设计的时候,为了方便检查和设计,时常需要将视图居中显示。一般地,会使用鼠标的中键进行放大和缩小,或者使用Zoom in和Zoom out来调整视图 Allegro还支持快速将视图居中 具体操作如下 点击View...
搜索相关功能
一、进入搜索页面 1.1 在pages下创建搜索页面为:search 1.2 在index.vue中点击进入搜素页面 onNavigationBarButtonTap(e){if(e.floatleft){uni.navigateTo({url:/pages/search/search})}},1.3 在pages.json中配置搜索页面头部 {"path" : "pages/…...
【从零开始制作 bt 下载器】一、了解 torrent 文件
【从零开始制作 bt 下载器】一、了解 torrent 文件写作背景了解 torrent 文件认识 bencodepython 解析 torrent 文件解密 torrent 文件结尾写作背景 最先开始是朋友向我诉说使用某雷下载结果显示因为版权无法下载,找其他的下载器有次数限制,于是来询问我…...
SystemVerilog-时序逻辑建模(5)多个时钟和时钟域交叉
数字硬件建模SystemVerilog-时序逻辑建模(5)多个时钟和时钟域交叉数字门级电路可分为两大类:组合逻辑和时序逻辑。锁存器是组合逻辑和时序逻辑的一个交叉点,在后面会作为单独的主题处理。组合逻辑描述了门级电路,其中逻…...
基本中型网络的仿真(RYU+Mininet的SDN架构)-以校园为例
目录 具体问题可以私聊博主 一、设计目标 1.1应用场景介绍 1.2应用场景设计要求 网络配置方式 网络技术要求 网络拓扑要求 互联互通 二、课程设计内容与原理 (1)预期网络拓扑结构和功能 (1)网络设备信息 …...
西北工业大学大学物理(II)期末试题选填解析2021-2022
2 金属薄片,就暗示了载流子是电子了。3 熟练掌握左右手即可。4 又是位移电流。6 感应电场。随时间变化着的磁场能在其周围空间激发一种电场,它能对处于其中的带电粒子施以力的作用,这就是涡旋电场,又叫感生电场。涡旋电场是非保守…...
【USB】windows热插拔通知接口分析
文章目录接口介绍概述过滤器介绍举例接收通知创建窗口参考文档接口介绍 概述 window提供了RegisterDeviceNotificationW方法,可以用来监听设备的热插拔事件。 HDEVNOTIFY RegisterDeviceNotificationW([in] HANDLE hRecipient,[in] LPVOID NotificationFilter,[in]…...
CMake入门
课程地址 文档地址 CMake可以用于所有的编程语言 HelloWorld 编写一个C文件: //hello.cpp #include <iostream>int main() {std::cout << "hello, world" <<std::endl;return 0; }手动编译: c hello.cpp书写CMakeList…...
python中一种编写config文件并及时更新的方法
contents0. Intro1. config.py2. 调用以及更新0. Intro 在pytorch或者其他深度学习框架中,有许多超参数需要调整,包括learning_rate,training_data_path等,因此编写一个config文件统一存放这些参数,方便调用/查看/修改…...
基于Windows下离线安装当前最新Arduino ESP32 SDK(2.0.7)固件开发包
基于Windows下离线安装当前最新Arduino ESP32 SDK(2.0.7)固件开发包✨写这篇的文章的初衷,是由于在前几天想通过离线一键安装包方式实现升级安装,结果发现解压后,可以找到开发板,但是无法上传代码ÿ…...
Android 9.0 app添加校验锁(输入密码才能进入app)
1.概述 在9.0的系统rom定制化开发中,在一些产品开发中,需要对app启动校验密码,输入密码后,才可以进app,所以说对这种 开发需求,首先找到启动app的关键点以后,在加入限制app启动的弹窗,输入密码,密码正确后在进入app,实现流程 就是这样,接下来看如何实现的 2.app添加校…...
注意力机制详解系列(二):通道注意力机制
👨💻作者简介: 大数据专业硕士在读,CSDN人工智能领域博客专家,阿里云专家博主,专注大数据与人工智能知识分享。 🎉专栏推荐: 目前在写CV方向专栏,更新不限于目标检测、…...
动态规划-规划兼职工作
动态规划-规划兼职工作 一、问题描述 你打算利用空闲时间来做兼职工作赚些零花钱。这里有 n 份兼职工作,每份工作预计从 startTime 开始到 endTime 结束,报酬为 profit。给你一份兼职工作表,包含开始时间 startTime,结束时间 en…...
日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘
美国西海岸的夏天,再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至,这不仅是开发者的盛宴,更是全球数亿苹果用户翘首以盼的科技春晚。今年,苹果依旧为我们带来了全家桶式的系统更新,包括 iOS 26、iPadOS 26…...
Linux链表操作全解析
Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表?1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以? 在 Golang 的面试中,map 类型的使用是一个常见的考点,其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...
【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...
定时器任务——若依源码分析
分析util包下面的工具类schedule utils: ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类,封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz,先构建任务的 JobD…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
