当前位置: 首页 > news >正文

【算法】【贪心算法】【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. 优势洗牌

题目地址&#xff1a;https://leetcode.cn/problems/advantage-shuffle/description/ 题目描述&#xff1a; 给定两个长度相等的数组 nums1 和 nums2&#xff0c;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&#xff1a;为字符串键设置值**** GETSET&#xff1a;获取旧值并设置新值**** MSET&#xff1a;一次为多个字符串键设置值**MGET&#xff1a;一次获取多个字符串键的值**** MSETNX&#xff1a;只在键不…...

嵌入式Linux学习第二天

今天学习linuxC编程。首先要熟悉linux下编写c程序的过程。 编写程序Hello World! 首先创建存放程序的文件夹&#xff0c;如下图所示&#xff1a; 接下来在创建一个文件夹来保存这节要编写的代码。指令&#xff1a;mkdir 3.1 接下来我们要设置VIM编辑器的一些配置&#xff0…...

【intro】图卷积神经网络(GCN)

本文为Graph Neural Networks(GNN)学习笔记-CSDN博客后续&#xff0c;内容为GCN论文阅读&#xff0c;相关博客阅读&#xff0c;kaggle上相关的数据集/文章/代码的阅读三部分&#xff0c;考虑到本人是GNN新手&#xff0c;会先从相关博客开始&#xff0c;进一步看kaggle&#xff…...

【Web】CTFSHOW 新手杯 题解

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

react 学习笔记二:ref、状态、继承

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

[SaaS]建筑领域的sd应用

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

气象数据nc数据矢量化处理解析及可视化

气象数据可视化是将气象学领域中复杂的数据集转化为图形或图像的过程&#xff0c;以直观展示天气现象、气候模式、趋势和预报结果。气象数据的可视化技术广泛应用于科学研究、气象预报、航空、航海、农业生产、灾害预警系统、城市规划、公众服务等领域。以下是一些关键的气象数…...

APP广告变现,开发者对接百度广告联盟,广告变现收益如何?

百度广告联盟属于广告整合平台&#xff0c;类似的还有穿山甲、优量汇、快手联盟等。 百度广告联盟注册流程&#xff1a; 创建账户&#xff1a;填写用户基本信息&#xff0c;如&#xff1a;用户名、密码、邮箱、手机号&#xff1b; 完善财务信息&#xff1a;填写银行账号、开…...

spring Ai框架整合Ollama,调用本地大模型

Ollama使用 Ollama是一个用于在本地计算机上运行大模型的软件 软件运行后监听11434端口&#xff0c;自己写的程序要调大模型就用这个端口 ollama命令 ollama list&#xff1a;显示模型列表 ollama show&#xff1a;显示模型的信息 ollama pull&#xff1a;拉取模型 ollama pu…...

八股spring+springboot+springMVC+Mybatis(一)

目录 1、面试官&#xff1a;Spring框架中的单例bean是线程安全的吗&#xff1f; 2、面试官&#xff1a;什么是AOP 3、面试官&#xff1a;你们项目中有没有使用到AOP 4、面试官&#xff1a;Spring中的事务是如何实现的 5、面试官&#xff1a;Spring中事务失效的场景有哪些 6、面…...

(六)SQL系列练习题(下)#CDA学习打卡

目录 三. 查询信息 16&#xff09;检索"1"课程分数小于60&#xff0c;按分数降序排列的学生信息​ 17&#xff09;*按平均成绩从高到低显示所有学生的所有课程的成绩以及平均成绩 18&#xff09;*查询各科成绩最高分、最低分和平均分 19&#xff09;*按各科成绩…...

python数据处理(pandas)

# 新的数据格式&#xff0c;csv纯文本&#xff0c;使用某个字符集&#xff0c;比如都是ASCII、Unicode、EBCDIC或GB2312&#xff08;简体中文环境&#xff09;等&#xff1b;由记录组成&#xff08;典型的是每行一条记录&#xff09;每条记录被分隔符&#xff08;英语&#xff…...

微信小程序开发秘籍:玩转麦克风录音与音频上传【代码示例】

微信小程序开发秘籍&#xff1a;玩转麦克风录音与音频上传【代码示例】 基本概念麦克风录音音频上传 实战演练1. 初始化录音功能2. 设计录音界面3. 实现音频上传安全性与性能优化 结语与讨论 在移动互联网时代&#xff0c;语音交互已成为提升用户体验的重要手段之一。微信小程序…...

spring的核心详解

Spring 核心详解 文章目录 Spring 核心详解前言什么是springspring的优点spring用到了哪些设计模式 什么是AOPAOP的实现方式静态代理动态代理 什么是IOCIOC的好处什么是依赖注入 前言 什么是spring Spring是一个开源的Java/Java EE全功能栈&#xff08;full-stack&#xff09…...

一、写给Android开发者之harmony入门

一、创建新项目 对比 android-studio&#xff1a;ability类似安卓activity ability分为两种类型(Stage模型) UIAbility和Extensionability&#xff08;提供系统服务和后台任务&#xff09; 启动模式 1、 singleton启动模式&#xff1a;单例 2、 multiton启动模式&#xff1…...

C++常用库函数——strstr、strcat

1、strstr&#xff1a;查找字符串子串函数&#xff0c;查找到的子串中第一个字符的地址&#xff0c;返回值是第一次出现子串字符串的位置。 例如&#xff1a; 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中的对象 对象&#xff08;object&#xff09;是JavaScript里的一种数据类型&#xff0c;可以理解为一种无序的数据集合&#xff08;数组是有序的数据集合…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

【磁盘】每天掌握一个Linux命令 - iostat

目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat&#xff08;I/O Statistics&#xff09;是Linux系统下用于监视系统输入输出设备和CPU使…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...

Linux系统部署KES

1、安装准备 1.版本说明V008R006C009B0014 V008&#xff1a;是version产品的大版本。 R006&#xff1a;是release产品特性版本。 C009&#xff1a;是通用版 B0014&#xff1a;是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存&#xff1a;1GB 以上 硬盘&#xf…...