【算法】【贪心算法】【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里的一种数据类型,可以理解为一种无序的数据集合(数组是有序的数据集合…...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
ffmpeg(四):滤镜命令
FFmpeg 的滤镜命令是用于音视频处理中的强大工具,可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下: ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜: ffmpeg…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
实战三:开发网页端界面完成黑白视频转为彩色视频
一、需求描述 设计一个简单的视频上色应用,用户可以通过网页界面上传黑白视频,系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观,不需要了解技术细节。 效果图 二、实现思路 总体思路: 用户通过Gradio界面上…...
Java中HashMap底层原理深度解析:从数据结构到红黑树优化
一、HashMap概述与核心特性 HashMap作为Java集合框架中最常用的数据结构之一,是基于哈希表的Map接口非同步实现。它允许使用null键和null值(但只能有一个null键),并且不保证映射顺序的恒久不变。与Hashtable相比,Hash…...
【记录坑点问题】IDEA运行:maven-resources-production:XX: OOM: Java heap space
问题:IDEA出现maven-resources-production:operation-service: java.lang.OutOfMemoryError: Java heap space 解决方案:将编译的堆内存增加一点 位置:设置setting-》构建菜单build-》编译器Complier...
如何让非 TCP/IP 协议驱动屏蔽 IPv4/IPv6 和 ARP 报文?
——从硬件过滤到协议栈隔离的完整指南 引言 在现代网络开发中,许多场景需要定制化网络协议(如工业控制、高性能计算),此时需确保驱动仅处理特定协议,避免被标准协议(如 IPv4/IPv6/ARP)干扰。本文基于 Linux 内核驱动的实现,探讨如何通过硬件过滤、驱动层拦截和协议栈…...
Qt Quick Dialogs模块功能及架构
Qt Quick Dialogs 是 Qt Quick 的一个附加模块,提供了一套用于创建和使用系统对话框的 QML 类型。在 Qt 6.0 中,这个模块经过了重构和增强。 一、主要功能和特点 1. 对话框类型 Qt Quick Dialogs 在 Qt 6.0 中提供了以下标准对话框类型: …...
低代码采购系统搭建:鲸采云+能源行业订单管理自动化案例
在能源行业数字化转型浪潮下,某大型能源集团通过鲸采云低代码平台,仅用3周时间就完成了采购订单管理系统的定制化搭建。本文将揭秘这一成功案例的实施路径与关键成效。 项目背景与挑战 该企业面临: 供应商分散:200供应商使用不同…...
django paramiko 跳转登录
在使用Django框架结合Paramiko进行SSH远程操作时,通常涉及到自动化脚本的执行,比如远程服务器上的命令执行、文件传输等。如果你的需求是“跳转登录”,即在登录远程服务器后,再通过该服务器的SSH连接跳转到另一台服务器࿰…...
