leetcode870.优势洗牌

server/2024/9/23 1:06:41/

题目描述:
 

给定两个长度相等的数组 nums1 和 nums2nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。

返回 nums1 的任意排列,使其相对于 nums2 的优势最大化。

示例一:

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

示例二:

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

问题解决:

本题主要是要将nums1对于nums2的优势最大化,其实就是将nums1打乱重组,使对应位置上的值

比nums2的值大的数目变的最多,所以我盟首先要做的工作是将两个数组排序,排序之后在通过比

比大小的方式俩对nums1进行重新排序,但是在比较的排序之前必须记录nums2的初识顺序,应为

要用nums2的初识顺序来决定nums1的最终顺序,我们可以用一个下标数组来记录nums2对应的下

标顺序,对应的具体代码如下:
 

class Solution 
{
public:vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {//1.排序int n = nums1.size();sort(nums1.begin(),nums1.end());vector<int> index2(n);for(int i = 0;i < n;i++){index2[i] = i;}sort(index2.begin(),index2.end(),[&](int i,int j){return nums2[i] < nums2[j];});//2.田忌赛马vector<int> ret(n);int left = 0,right = n - 1;for(auto x: nums1){if(x > nums2[index2[left]]){ret[index2[left++]] = x;}else{ret[index2[right--]] = x;}}return ret;}
};

对应以示例二进行演示代码:

由上图可知,在比较的时候其实nums2的位置没有发生真是改变,而是通过下标对应进行了对

nums2的排序,而最终在对nums1排序的时候使用的是田忌赛马的方法,如果nums1的最小比不

过nums2的最小,直接将nums1的最小放在最后,取对抗最大的那个数,反之,如果nums1对应的

位置数较大,直接用来对抗nums2对应位置的数,这就是这道题的基本原理,


http://www.ppmy.cn/server/30076.html

相关文章

【软件工程】习题一

目录 一二三四五 一 软件工程学&#xff0c;是用工程化的方法指导计算机软件**开发和维护&#xff08;开发和管理&#xff09;**的一门工程学科。 软件工程包括软件开发技术&#xff08;过程、方法和工具&#xff09;与软件工程管理两方面的内容。 软件工程管理是通过计划、组…

华为OD试题: 猴子爬山思路和代码

猴子爬山不管用递归法最简单思路也最清晰 不管阶梯的数量&#xff0c;最后登顶方法只有跳一阶或者三阶&#xff0c;并且前面只有当阶梯为2的时候这种特殊情况&#xff0c;只能跳一阶 所以代码可以这样写 def news(num):if num<2:return 1if num3:return 2return news(num-…

cmd查看局域网内所有设备ip

说明&#xff1a;最近碰到一个新问题&#xff0c;就是有一个安卓设备&#xff0c;安装了一个app导致死机了&#xff0c;app设置了开机重启&#xff0c;所以&#xff0c;无论重启还是关机&#xff0c;都是进来就白屏&#xff0c; 这可把人愁坏了&#xff0c;直接死循环了 无论…

发卡盗u源码系统搭建ZHU

2024最新UI发卡盗U/支持多语言/更新UI界面/支持多个主流钱包去除后门板&#xff0c;最好是部署智能合约后用合约地址来授权包含转账支付页面盗U授权源码。 完美提U&#xff0c;教程包含如何提u 。功能完美。 1.Php静态 2.目录puicta 3.扩sal 4.ssl不强https

RCD吸收电路:开关电源高频干扰的有效消除器

开关电源中除了我们常规介绍的差模噪声源和共模噪声源&#xff0c;还存在一些其它的噪声源也应该解决&#xff0c;这些高频噪声源同样会带来电磁兼容问题&#xff0c;因此我们需要关注。这里介绍两种干扰源&#xff0c;一种是MOS管的通断带来的高频振荡噪声&#xff0c;另一种是…

VScode Failed to parse remote port from server output

在使用VScode 在连接AutoDL 过程中一直连接不上&#xff0c;显示 Failed to parse remote port from server output 在网上查了很多资料&#xff0c;貌似的没啥用。和我有相同 error 的可以尝试修改setting.json 文件。 添加这条命令&#xff08;我的json文件里面没有&#…

计算机408备考-数据结构重要知识点-数据结构的定义

请关注一下B站账号&#xff1a;谭同学很nice&#xff01;后期更新发布在这个账号上。。【计算机408备考-数据结构重要知识点-数据结构的定义-哔哩哔哩】https://b23.tv/x7shjNf 数据是信息的载体。数据元素是数据的基本单位。一个数据元素可由若干数据项组成&#xff0c;数据项…

《有限元分析及应用》《有限元分析基础教程》-曾攀-清华大学|pdf电子书+有限元分析及应用视频教程(全85讲) 曾攀、雷丽萍 ​​​+课件PPT

专栏导读 作者简介&#xff1a;工学博士&#xff0c;高级工程师&#xff0c;专注于工业软件算法研究本文已收录于专栏&#xff1a;《有限元编程从入门到精通》本专栏旨在提供 1.以案例的形式讲解各类有限元问题的程序实现&#xff0c;并提供所有案例完整源码&#xff1b;2.单元…