【算法】【贪心算法】【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;}
}
相关文章:

【算法】【贪心算法】【leetcode】870. 优势洗牌
题目地址:https://leetcode.cn/problems/advantage-shuffle/description/ 题目描述: 给定两个长度相等的数组 nums1 和 nums2,nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。 返回 nums1 的任意排列&…...

Unity AVProVideo安卓播放视频问题
打包ARM64,插件里arm64里的几个库都设置arm64,平台选择安卓 Unity VideoPlayer使用url方式,Android平台下无法播放http链接的视频 主要原因:默认情况下,不允许从Android 8开始使用不安全的HTTP,并且必须使用HTTPS,除非分配了自定义的明文安全策略 解决办法: 只需要修…...
Redis使用手册之字符串
《Redis使用手册字符串设置》 目录 **《Redis使用手册字符串设置》**** SET:为字符串键设置值**** GETSET:获取旧值并设置新值**** MSET:一次为多个字符串键设置值**MGET:一次获取多个字符串键的值**** MSETNX:只在键不…...

嵌入式Linux学习第二天
今天学习linuxC编程。首先要熟悉linux下编写c程序的过程。 编写程序Hello World! 首先创建存放程序的文件夹,如下图所示: 接下来在创建一个文件夹来保存这节要编写的代码。指令:mkdir 3.1 接下来我们要设置VIM编辑器的一些配置࿰…...
【intro】图卷积神经网络(GCN)
本文为Graph Neural Networks(GNN)学习笔记-CSDN博客后续,内容为GCN论文阅读,相关博客阅读,kaggle上相关的数据集/文章/代码的阅读三部分,考虑到本人是GNN新手,会先从相关博客开始,进一步看kaggleÿ…...

【Web】CTFSHOW 新手杯 题解
目录 easy_eval 剪刀石头布 baby_pickle repairman easy_eval 用script标签来绕过 剪刀石头布 需要赢100轮🤔 右键查看源码拿到提示 一眼session反序列化 打PHP_SESSION_UPLOAD_PROGRESS 脚本 import requestsp1 a|O:4:"Game":1:{s:3:"log…...

react 学习笔记二:ref、状态、继承
基础知识 1、ref 创建变量时,需要运用到username React.createRef(),并将其绑定到对应的节点。在使用时需要获取当前的节点; 注意:vue直接使用里面的值,不需要再用this。 2、状态 组件描述某种显示情况的数据&#…...

[SaaS]建筑领域的sd应用
AirchiDesignhttp://www.aiarchi.art/#/建筑学长——千万建筑师的资源库和AI绘图创作平台建筑学长官网,为青年设计师建立的线上资源共享及AI绘图创作渲染平台,免费提供海量设计案例、CAD图纸、SU模型、PS素材、软件插件下载,提供丰富的设计软件教学与灵感参考素材图库。https:/…...

气象数据nc数据矢量化处理解析及可视化
气象数据可视化是将气象学领域中复杂的数据集转化为图形或图像的过程,以直观展示天气现象、气候模式、趋势和预报结果。气象数据的可视化技术广泛应用于科学研究、气象预报、航空、航海、农业生产、灾害预警系统、城市规划、公众服务等领域。以下是一些关键的气象数…...
APP广告变现,开发者对接百度广告联盟,广告变现收益如何?
百度广告联盟属于广告整合平台,类似的还有穿山甲、优量汇、快手联盟等。 百度广告联盟注册流程: 创建账户:填写用户基本信息,如:用户名、密码、邮箱、手机号; 完善财务信息:填写银行账号、开…...
spring Ai框架整合Ollama,调用本地大模型
Ollama使用 Ollama是一个用于在本地计算机上运行大模型的软件 软件运行后监听11434端口,自己写的程序要调大模型就用这个端口 ollama命令 ollama list:显示模型列表 ollama show:显示模型的信息 ollama pull:拉取模型 ollama pu…...
八股spring+springboot+springMVC+Mybatis(一)
目录 1、面试官:Spring框架中的单例bean是线程安全的吗? 2、面试官:什么是AOP 3、面试官:你们项目中有没有使用到AOP 4、面试官:Spring中的事务是如何实现的 5、面试官:Spring中事务失效的场景有哪些 6、面…...

(六)SQL系列练习题(下)#CDA学习打卡
目录 三. 查询信息 16)检索"1"课程分数小于60,按分数降序排列的学生信息 17)*按平均成绩从高到低显示所有学生的所有课程的成绩以及平均成绩 18)*查询各科成绩最高分、最低分和平均分 19)*按各科成绩…...
python数据处理(pandas)
# 新的数据格式,csv纯文本,使用某个字符集,比如都是ASCII、Unicode、EBCDIC或GB2312(简体中文环境)等;由记录组成(典型的是每行一条记录)每条记录被分隔符(英语ÿ…...
微信小程序开发秘籍:玩转麦克风录音与音频上传【代码示例】
微信小程序开发秘籍:玩转麦克风录音与音频上传【代码示例】 基本概念麦克风录音音频上传 实战演练1. 初始化录音功能2. 设计录音界面3. 实现音频上传安全性与性能优化 结语与讨论 在移动互联网时代,语音交互已成为提升用户体验的重要手段之一。微信小程序…...
spring的核心详解
Spring 核心详解 文章目录 Spring 核心详解前言什么是springspring的优点spring用到了哪些设计模式 什么是AOPAOP的实现方式静态代理动态代理 什么是IOCIOC的好处什么是依赖注入 前言 什么是spring Spring是一个开源的Java/Java EE全功能栈(full-stack)…...

一、写给Android开发者之harmony入门
一、创建新项目 对比 android-studio:ability类似安卓activity ability分为两种类型(Stage模型) UIAbility和Extensionability(提供系统服务和后台任务) 启动模式 1、 singleton启动模式:单例 2、 multiton启动模式࿱…...

C++常用库函数——strstr、strcat
1、strstr:查找字符串子串函数,查找到的子串中第一个字符的地址,返回值是第一次出现子串字符串的位置。 例如: char a[20] "RUNOOB"; char b[10] "NOOB"; printf("%s", strstr(a, b)); 在这里…...
Kafak 消费异常:The coordinator is not available.
Kafak 消费异常:The coordinator is not available. 1. 问题描述2. 问题排查2.1 Topic 状态异常2.2 `__consumer_offsets` 简介1. 问题描述 在新环境部署 Kafak 时,发现可以正常产生消息,但是无法正常消费消息,消费消息的异常日志如下: 11:59:53.315 [main] DEBUG org.a…...
JavaScript中的对象
这里写目录标题 JavaScript中的对象属性 对象的使用属性和访问方法和调用遍历对象null 内置对象Math属性方法 JavaScript中的对象 对象(object)是JavaScript里的一种数据类型,可以理解为一种无序的数据集合(数组是有序的数据集合…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...

(十)学生端搭建
本次旨在将之前的已完成的部分功能进行拼装到学生端,同时完善学生端的构建。本次工作主要包括: 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...

visual studio 2022更改主题为深色
visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中,选择 环境 -> 常规 ,将其中的颜色主题改成深色 点击确定,更改完成...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...

12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习
禁止商业或二改转载,仅供自学使用,侵权必究,如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...
Java数值运算常见陷阱与规避方法
整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...
08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险
C#入门系列【类的基本概念】:开启编程世界的奇妙冒险 嘿,各位编程小白探险家!欢迎来到 C# 的奇幻大陆!今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类!别害怕,跟着我,保准让你轻松搞…...