【算法】【贪心算法】【leetcode】870. 优势洗牌

在这里插入图片描述
题目地址:https://leetcode.cn/problems/advantage-shuffle/description/

题目描述:

给定两个长度相等的数组 nums1 和 nums2,nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i]
的索引 i 的数目来描述。 返回 nums1 的任意排列,使其相对于 nums2 的优势最大化。

示例 1:

输入:nums1 = [2,7,11,15], nums2 = [1,10,4,11]
输出:[2,11,7,15]

示例 2:

输入:nums1 = [12,24,8,32], nums2 = [13,25,32,11]
输出:[24,32,8,12]

提示:

1 <= nums1.length <= 10^5
nums2.length == nums1.length
0 <= nums1[i] ,nums2[i] <= 10^9

解题思路(典型贪心算法)

田忌赛马的故事大家应该都听说过: 田忌和齐王赛马,两人的马分上中下三等,如果同等级的马对应着比赛,田忌赢不了齐王。但是田忌遇到了孙膑,
孙膑就教他用自己的下等马对齐王的上等马,再用自己的上等马对齐王的中等马,最后用自己的中等马对齐王的下等马,结果三局两胜,田忌赢了。
田忌赛马的核心思路就是打得过就打,打不过就拿自己的垃圾和对方的精锐互换。

把nums1当成是田忌的马,nums2当成是齐威王的马。 讨论田忌的下等马(nums的最小值):

  • 如果它能比过齐威王的下等马(nums的最小值),那这一分田忌直接拿下;

  • 如果它比不过齐威王的下等马,则用田忌的下等马比齐威王的上等马(mums2的最大值)。

去掉这两匹马,问题变成一个规模更小(n-1)的子问题。重复上述过程,即得到了所有马的对应 关系。

代码实现时,由于num2不能排序,我们可以创建一个下标数组ids,对ids排序,即ids[0]对应
nums2中最小值的下标,ids[1]对应num2中第二小值的下标。用双指针操作ids,从而知道
每个下标所要对应的nums1的元素,也就找到了所要求的nums1的排列。

解题思路来自:(灵茶山艾府)https://leetcode.cn/problems/advantage-shuffle/solutions/1/tian-ji-sai-ma-by-endlesscheng-yxm6/

代码实现

public class Solution{public int[] advantageCount(int[] nums1, int[] nums2) {//先对nums1进行排序Arrays.sort(nums1);//对muns2排序 但是mums2不能直接排序 需要额外借助一个数据排序int nums2Len = nums2.length;int [] ids = new int [nums2Len];//记录nums2的下标for(int i =0;i<n;i++){ids[i]=i;}//将num2进行排序 注意这里不能直接对nums2排序 转对nums2的下标排序代替nums2的顺序//升序排列 (降序也是一个样)Arrays.sort(ids,(i,j)->nums2[i]-nums2[j]);//赛马:打得过就打,打不过就拿自己的垃圾和对方的精锐互换int [] ans = new int[nums1.length];int right = nums2Len;int left = 0;for (int x : nums1) {ans[x > nums2[ids[left]] ? ids[left++] : ids[right--]] = x;}return ans;}
}

在这里插入图片描述

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

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

相关文章

HTML5(1)

目录 一.HTML5(超文本&#xff08;链接&#xff09;标记&#xff08;标签<>&#xff09;语言) 1.开发环境&#xff08;写代码&#xff0c;看效果&#xff09; 2.vscode 使用 3.谷歌浏览器使用 4.标签语法 5.HTML基本骨架&#xff08;网页模板&#xff09; 6.标签的…

【配置】Docker搭建JSON在线解析网站

云服务器打开端口8787 连接上docker运行 docker run -id --name jsonhero -p 8787:8787 -e SESSION_SECRETabc123 henryclw/jsonhero-webhttp://ip:8787访问 Github&#xff1a;地址

透视天气:数据可视化的新视角

数据可视化在天气方面能够为我们带来极大的帮助。天气是人类生活中一个重要的因素&#xff0c;对于农业、交通、航空、能源等各个领域都有着重要的影响。而数据可视化技术通过将复杂的天气数据转化为直观、易懂的图表、图像或地图等形式&#xff0c;为我们提供了更深入、更全面…

接口测试 - postman

文章目录 一、接口1.接口的类型2. 接口测试3. 接口测试流程4. 接口测试用例1. 测试用例单接口测试用例-登录案例 二、HTTP协议1. HTTP请求2. HTTP响应 三、postman1. 界面导航说明导入 导出用例集 Get请求和Post请求的区别:2.postman环境变量和全局变量3. postman 请求前置脚本…

ECharts在网页中添加可视化图标-在网页中添加交互图表+option模块案列详解

一、引言 ECharts 是一个使用 JavaScript 编写的开源可视化库&#xff0c;它可以在浏览器中生成交互式的图表。无论是折线图、柱状图、散点图还是饼图&#xff0c;ECharts 都能轻松应对。本文将带领大家了解如何在网页中添加 ECharts 可视化图标。 本章可以直接跳到第五点完整…

【Spring基础】关于Spring IoC的那些事

文章目录 一、如何理解IoC1.1 Spring IOC 概述1.2 IoC 是什么 二、Ioc 配置的方式2.1 xml 配置2.2 Java 配置2.3 注解配置 三、依赖注入的方式3.1 setter方式3.2 构造函数3.3 注解注入 小结 一、如何理解IoC 1.1 Spring IOC 概述 控制反转 IoC(Inversion of Control)是一种设计…

2024数学建模时间汇总与竞赛攻略

目录 2024数学建模汇总&#xff08;时间、报名费、获奖率、竞赛级别、是否可跨校&#xff09; 中国高校大数据挑战赛 “华数杯”国际大学生数学建模竞赛 美国大学生数学建模竞赛&#xff08;美赛&#xff09; 数学中国&#xff08;认证杯&#xff09;数学建模网络挑战赛 …

解决RuntimeError: cuDNN error: CUDNN_STATUS_EXECUTION_FAILED

下图说明在一瞬间我的GPU就被占满了 我的模型在训练过程中遇到了 CUDA 相关的错误&#xff0c;这是由于 GPU资源问题或内存不足导致的。这类错误有时候也可能是由于某些硬件兼容性问题或驱动程序问题引起的。 为了解决这个问题&#xff0c;可以尝试以下几个解决方案&#xff1a…

【Godot4.2】有序和无序列表函数库 - myList

概述 在打印输出或其他地方可能需要构建有序或无序列表。本质就是构造和维护一个纯文本数组。并用格式化文本形式&#xff0c;输出带序号或前缀字符的多行文本。 为此我专门设计了一个类myList&#xff0c;来完成这项任务。 代码 以下是myList类的完整代码&#xff1a; # …

模型剪枝-Network Slimming算法分析

代码见文末 论文地址&#xff1a;Learning Efficient Convolutional Networks through Network Slimming ICCV 2017 Open Access Repository 1.概述 由于边缘设备的限制&#xff0c;在模型的部署中经常受到模型大小、运行内存、计算量的限制。之前的方法要么只能解决其中一个…

spark实验求TOP值

实验1&#xff1a;求TOP值 已知存在两个文本文件&#xff0c;file1.txt和file2.txt&#xff0c;内容分别如下&#xff1a; file1.txt 1,1768,50,155 2,1218, 600,211 3,2239,788,242 4,3101,28,599 5,4899,290,129 6,3110,54,1201 7,4436,259,877 8,2369,7890,27 fil…

合泰杯(HT32F52352)RTC的应用(计时)--->掉电不丢失VBAT(代码已经实现附带源码)

摘要 在HT32F52352合泰单片机开发中&#xff0c;rtc在网上还是挺少人应用的&#xff0c;找了很久没什么资料&#xff0c;现在我根据手册和官方的代码进行配置理解。 RTC在嵌入式单片机中是一个很重要的应用资源。 记录事件时间戳&#xff1a;RTC可以记录事件发生的精确时间&…

STL——stackqueue

stack stack即为栈&#xff0c;先进后出是其特点 栈只有栈顶元素能被外界使用&#xff0c;故不存在遍历行为 栈中常用接口 构造函数 stack<T> stk; //默认构造方式 stack(const stack &stk); //拷贝构造 赋值操作 stack& operator(const stack &stk); …

动手学深度学习——softmax分类

1. 分类问题 回归与分类的区别&#xff1a; 回归可以用于预测多少的问题&#xff0c; 比如"预测房屋被售出价格"&#xff0c;它是个单值输出。softmax可以用来预测分类问题&#xff0c;例如"某个图片中是猫、鸡还是狗&#xff1f;"&#xff0c;这是一个多…

Apache POI 在java中处理excel

介绍: Apache POI 是一个处理Miscrosoft Office各种文件格式的开源项目。简单来说就是&#xff0c;我们可以使用 POI 在 Java 程序中对Miscrosoft Office各种文件进行读写操作。 一般情况下&#xff0c;POI 都是用于操作 Excel 文件。 如何使用: 1.maven坐标引入 <depend…

安卓获取SHA

1&#xff1a;安卓通过签名key获取SHA 方式有两种&#xff0c; 1、电脑上来存在eclipse的用户或正在使用此开发工具的用户就简单了&#xff0c;直接利用eclipse 走打包流程&#xff0c;再打包的时候选择相应的签名&#xff0c;那么在当前面板的下面便会出现签名的相关信息。 2、…

iOS实现一个高性能的跑马灯

效果图 该跑马灯完全通过CATextLayer 实现&#xff0c;轻量级&#xff0c;并且通过 系统的位移动画实现滚动效果&#xff0c;避免了使用displaylink造成的性能瓶颈&#xff0c;使用系统动画&#xff0c;系统自动做了很多性能优化&#xff0c;实现更好的性能&#xff0c;并使用…

ChatGPT 网络安全秘籍(四)

原文&#xff1a;zh.annas-archive.org/md5/6b2705e0d6d24d8c113752f67b42d7d8 译者&#xff1a;飞龙 协议&#xff1a;CC BY-NC-SA 4.0 第八章&#xff1a;事故响应 事故响应是任何网络安全策略的关键组成部分&#xff0c;涉及确定、分析和缓解安全漏洞或攻击。 及时和有效地…

LLM应用:让大模型prompt总结生成Mermaid流程图

生成内容、总结文章让大模型Mermaid流程图展示&#xff1a; mermaid 美人鱼, 是一个类似 markdown&#xff0c;用文本语法来描述文档图形(流程图、 时序图、甘特图)的工具&#xff0c;您可以在文档中嵌入一段 mermaid 文本来生成 SVG 形式的图形 Prompt 示例&#xff1a;用横向…

数智新重庆 | 推进信号升格 打造算力山城

2024年&#xff0c;是实现“十四五”规划目标任务的关键一年&#xff0c;高质量的5G网络、强大的AI能力作为新质生产力的重要组成部分&#xff0c;将有效赋能包括制造业在内的千行万业数字化化、智能化、绿色化转型升级&#xff0c;推动融合应用新业态、新模式蓬勃兴起&#xf…