【LeetCode】870 . 优势洗牌

870 . 优势洗牌

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

方法:贪心

思路

  • 这道题的思想类似于 “田忌赛马” ,把 nums1 当成是田忌的马,nums2 当成是齐威王的马。

  • 讨论田忌的下等马(nums1 的最小值):

    • 如果它能比过齐威王的下等马(nums2 的最小值),那这一分田忌直接拿下;
    • 如果它比不过齐威王的下等马,则用田忌的下等马比齐威王的上等马(nums2 的最大值)。
  • 去掉这两匹马,问题变成一个规模更小(n−1 )的子问题。重复上述过程,即得到了所有马的对应关系。

  • 代码实现时,直接对 nums1 进行排序,由于我们后续还需用用到 nums2 的下标,因此不能直接对 nums2 排序。而是用 multiset 来保存 nums2 的值和下标,同时,该数据结构会对 nums2 自动排序(从小到大),且允许存在重复值。

  • 注意:erase函数的使用

    void erase ( iterator position ) ,它的参数只能是正向迭代器,我一开始使用了 rbegin() 用于删除最后一个值,而 rbegin 的类型是 reverse_iterator ,所以一直出错。

代码

class Solution {
public:vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {// 创建一个答案数组vector<int> ans(nums1.size());// 先将nums1重新排序sort(nums1.begin(), nums1.end());// 创建一个多重映射,从小到大保存nums2的值及其下标// 这里需要使用multimap,因为nums2中可能存在重复的值multimap<int, int> mp;for(int i=0; i<nums2.size(); ++i){mp.insert({nums2[i], i});}for(int i=0; i<nums1.size(); ++i){// "田忌赛马" 如果nums1的最小值大于nums2的最小值,就以此赢他if(nums1[i] > mp.begin()->first){ans[mp.begin()->second] = nums1[i];mp.erase(mp.begin());}// 否则就用nums1的最小值和nums2的最大值相比else{ans[mp.rbegin()->second] = nums1[i];mp.erase(--mp.end());} }return ans;}
};

参考文献

  1. 田忌赛马(Python/Java/C++/Go)

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

AD域机器KMS自动激活

1、打开AD域控&#xff0c;点击DNS管理 2、创建其它记录 3、选择服务位置 SRV 4、输入相关信息 服务&#xff1a;_VLMCS协议&#xff1a;_TCP权重&#xff1a;100端口号&#xff1a;1688KMS服务器地址&#xff1a;10.3.0.211 5、成功&#xff0c;这时域内主机重启后&#xff0…

第48节:cesium 面交集计算(含源码+视频)

结果示例: 完整源码: <template><div class="viewer"><vc-viewer @ready="ready" :logo="false"><vc-navigation

postgresql之内存池-GenerationContext

创建GenerationContext MemoryContext GenerationContextCreate(MemoryContext parent,const char *name,Size blockSize) {GenerationContext *set; ...set (GenerationContext *) malloc(MAXALIGN(sizeof(GenerationContext))); .../* Fill in GenerationContext-specific …

Angular安全专辑 —— CSP防止XSS攻击

什么是 CSP&#xff08;Content Security Policy&#xff09; CSP&#xff08;Content Security Policy&#xff09;是一种Web安全策略&#xff0c;用于减轻和防止跨站脚本攻击&#xff08;XSS&#xff09;等安全漏洞。它通过允许网站管理员定义哪些资源可以加载到网页中&#…

计算机网络(8) --- IP与IP协议

计算机网络&#xff08;7&#xff09; --- UDP协议和TCP协议_哈里沃克的博客-CSDN博客UDP协议和TCP协议https://blog.csdn.net/m0_63488627/article/details/132125374?spm1001.2014.3001.5501 目录 1.IP与IP协议 IP作用 协议​编辑 2.网段划分 DHCP划分 CIDR划分 特殊…

旷视科技AIoT软硬一体化走向深处,生态和大模型成为“两翼”?

齐奏AI交响曲的当下&#xff0c;赛道玩家各自精彩。其中&#xff0c;被称作AI四小龙的商汤科技、云从科技、依图科技、旷视科技已成长为业内标杆&#xff0c;并积极追赶新浪潮。无论是涌向二级市场还是布局最新风口大模型&#xff0c;AI四小龙谁都不甘其后。 以深耕AIoT软硬一…

大语言模型之三 InstructGPT训练过程

大语言模型 GPT历史文章中简介的大语言模型的的发展史&#xff0c;并且简要介绍了大语言模型的训练过程&#xff0c;本篇文章详细阐述训练的细节和相关的算法。 2020年后全球互联网大厂、AI创业公司研发了不少AI超大模型&#xff08;百亿甚至千亿参数&#xff09;&#xff0c;…

人大金仓三大兼容:Oracle迁移无忧

企业级应用早期的架构模式是C/S&#xff08;Client/Server&#xff09;模式&#xff0c;Client做人机交互逻辑的呈现&#xff0c;Sever做业务计算逻辑的实现。这就类似餐馆的运作模式&#xff0c;Client是前台的服务员提供点菜和上菜服务&#xff0c;而Server则是后厨完成菜品的…

【论文阅读】基于深度学习的时序异常检测——TransAD

系列文章链接 数据解读参考&#xff1a;数据基础&#xff1a;多维时序数据集简介 论文一&#xff1a;2022 Anomaly Transformer&#xff1a;异常分数预测 论文二&#xff1a;2022 TransAD&#xff1a;异常分数预测 论文三&#xff1a;2023 TimesNet&#xff1a;基于卷积的多任务…

角角の Qt学习笔记(一)

目录 一、解决在创建新项目时遇到的几个问题 二、信号和槽&#xff08;非自定义&#xff09; 三、调用 UI 中的元素&#xff08;比如按钮&#xff09; 一、解决在创建新项目时遇到的几个问题 在新建项目时&#xff0c;我选择的构建系统为CMake。然后勾选了Generate form&…

各地区-各行业法人单位、区划数63个指标(2010-2022年)

一、数据介绍 数据名称&#xff1a;各地区-各行业法人单位、区划数63个指标 数据年份&#xff1a;2010-2022年&#xff08;法人单位至2021年&#xff09; 数据样本&#xff1a;404条 数据来源&#xff1a;自我整理 二、指标说明 行政区划代码 地区 长江经济带 经度 纬…

CAP理论与MongoDB一致性,可用性的一些思考

正文 大约在五六年前&#xff0c;第一次接触到了当时已经是hot topic的NoSql。不过那个时候学的用的都是mysql&#xff0c;Nosql对于我而言还是新事物&#xff0c;并没有真正使用&#xff0c;只是不明觉厉。但是印象深刻的是这么一张图片&#xff08;后来google到图片来自这里&…

Java实现对称加密(DES,AES)快速入门示例

对称加密是使用相同的密码进行加密和解密&#xff0c; 对称加密实现简单&#xff0c;安全性相比非对称加密较弱&#xff0c; 常用的对称加密算法有 DES&#xff0c;AES以及PDE等&#xff0c;关于对称加密相关概念参考&#xff1a; 对称加密、非对称加密深度解析 本篇介绍Java的…

python——案例17:判断某年是否是闰年

案例17&#xff1a;判断某年是否是闰年 判断依据&#xff1a;闰年就是能被400整除&#xff0c;或者能被4整除的年份numint(input(输入年份&#xff1a;))if num%1000: if num%4000: #整百年份的判断print("%s年是闰年"%num) #…

设计模式行为型——状态模式

目录 状态模式的定义 状态模式的实现 状态模式角色 状态模式类图 状态模式举例 状态模式代码实现 状态模式的特点 优点 缺点 使用场景 注意事项 实际应用 在软件开发过程中&#xff0c;应用程序中的部分对象可能会根据不同的情况做出不同的行为&#xff0c;把这种对…

flutter开发实战-实现marquee根据文本长度显示文本跑马灯效果

flutter开发实战-实现marquee文本跑马灯效果 最近开发过程中需要marquee文本跑马灯效果&#xff0c;这里使用到了flutter的插件marquee 效果图如下 一、marquee 1.1 引入marquee 在pubspec.yaml中引入marquee # 跑马灯效果marquee: ^2.2.31.2 marquee使用 marquee使用也是…

谈谈对Spring MVC的理解

问题分析&#xff1a; SpringMVC 是一种基于 Java 语言开发&#xff0c;实现了 Web MVC 设计模式&#xff0c;请求驱动类型 的轻量级 Web 框架。 SpringMVC采用了 MVC 架构模式的思想&#xff0c;通过把 Model&#xff0c;View&#xff0c;Controller 分离&#xff0c;将 Web 层…

易服客工作室:如何在WordPress网站中举办虚拟活动

您是否正在寻找举办和管理虚拟活动的最佳方式&#xff1f; 也许您想在线举行下一次会议或举办有关您的产品和服务的网络研讨会。您可能担心它太贵&#xff0c;或者您没有技术知识来实现​​它。 在本文中&#xff0c;我们将列出您所需的在线服务的所有设备&#xff0c;并教您…

实践指南-前端性能提升 270% | 京东云技术团队

一、背景 当我们疲于开发一个接一个的需求时&#xff0c;很容易忘记去关注网站的性能&#xff0c;到了某一个节点&#xff0c;猛地发现&#xff0c;随着越来越多代码的堆积&#xff0c;网站变得越来越慢。 本文就是从这样的一个背景出发&#xff0c;着手优化网站的前端性能&a…

在R中比较两个矩阵是否相等

目录 方法一&#xff1a;使用all.equal()比较两个R对象是否近似相等 方法二&#xff1a;使用identical比较两个R对象是否精确相等。 方法一&#xff1a;使用all.equal()比较两个R对象是否近似相等 使用函数&#xff1a;all.equal(x,y) 比较两个R对象x和y是否近似相等 > M1…