3072. 将元素分配到两个数组中 II Hard

给你一个下标从 1 开始、长度为 n 的整数数组 nums 。

现定义函数 greaterCount ,使得 greaterCount(arr, val) 返回数组 arr 中 严格大于 val 的元素数量。

你需要使用 n 次操作,将 nums 的所有元素分配到两个数组 arr1 和 arr2 中。在第一次操作中,将 nums[1] 追加到 arr1 。在第二次操作中,将 nums[2] 追加到 arr2 。之后,在第 i 次操作中:

 ·如果 greaterCount(arr1, nums[i]) > greaterCount(arr2, nums[i]) ,将 nums[i] 追加到 arr1 。

 ·如果 greaterCount(arr1, nums[i]) < greaterCount(arr2, nums[i]) ,将 nums[i] 追加到 arr2 。

 ·如果 greaterCount(arr1, nums[i]) == greaterCount(arr2, nums[i]) ,将 nums[i] 追加到元素数量较少的数组中。

 ·如果仍然相等,那么将 nums[i] 追加到 arr1 。

连接数组 arr1 和 arr2 形成数组 result 。例如,如果 arr1 == [1,2,3] 且 arr2 == [4,5,6] ,那么 result = [1,2,3,4,5,6] 。

返回整数数组 result 。

示例 1:

输入:nums = [2,1,3,3]
输出:[2,3,1,3]
解释:在前两次操作后,arr1 = [2] ,arr2 = [1] 。
在第 3 次操作中,两个数组中大于 3 的元素数量都是零,并且长度相等,因此,将 nums[3] 追加到 arr1 。
在第 4 次操作中,两个数组中大于 3 的元素数量都是零,但 arr2 的长度较小,因此,将 nums[4] 追加到 arr2 。
在 4 次操作后,arr1 = [2,3] ,arr2 = [1,3] 。
因此,连接形成的数组 result 是 [2,3,1,3] 。

示例 2:

输入:nums = [5,14,3,1,2]
输出:[5,3,1,2,14]
解释:在前两次操作后,arr1 = [5] ,arr2 = [14] 。
在第 3 次操作中,两个数组中大于 3 的元素数量都是一,并且长度相等,因此,将 nums[3] 追加到 arr1 。
在第 4 次操作中,arr1 中大于 1 的元素数量大于 arr2 中的数量(2 > 1),因此,将 nums[4] 追加到 arr1 。
在第 5 次操作中,arr1 中大于 2 的元素数量大于 arr2 中的数量(2 > 1),因此,将 nums[5] 追加到 arr1 。
在 5 次操作后,arr1 = [5,3,1,2] ,arr2 = [14] 。
因此,连接形成的数组 result 是 [5,3,1,2,14] 。

示例 3:

输入:nums = [3,3,3,3]
输出:[3,3,3,3]
解释:在 4 次操作后,arr1 = [3,3] ,arr2 = [3,3] 。
因此,连接形成的数组 result 是 [3,3,3,3] 。

提示:

 ·3 <= n <= 105

 ·1 <= nums[i] <= 109

题目大意:按照规则在两个新数组中添加原数组的元素,返回两个新数组拼接后的数组。

分析:

(1)添加元素需依据两个新数组中严格大于当前元素的元素数量,如果采用线性统计的方式,整个算法的时间复杂度达到O(N2),而数据规模为105,因此在该时间复杂度下会超时。由此可见本题的关键是需要设计时间复杂度更小的数据统计算法;

(2)基于(1),考虑使用树状数组快速查找数组中严格大于val的元素数量,分别对两个新数组arr1和arr2设立对应的树状数组tree1和tree2,用于记录两个数组中出现的元素。遍历到原数组的i号元素时就可以用树状数组分别计算两个新数组中严格大于nums[i]的元素数量;

(3)由于元素放入哪个数组仅与该元素和其它元素的大小关系相关,因此可将数组中的元素按大小关系离散化。

class BinaryIndexedTree{
public:BinaryIndexedTree(int N):_N(N+1),_tree(N+1){}void add(int i){while(i<_N){++_tree[i];i+=i&(-i);}}int count(int i){int ans=0;while(i>0){ans+=_tree[i];i-=i&(-i);}return ans;}
private:vector<int> _tree;int _N;
};
class Solution {
public:vector<int> resultArray(vector<int>& nums) {int N=nums.size(),sum1,sum2;vector<int> arr1={nums[0]},arr2={nums[1]},newNums=nums;unordered_map<int,int> index;BinaryIndexedTree tree1(N+1),tree2(N+1);sort(newNums.begin(),newNums.end());for(int i=0;i<N;++i) index[newNums[i]]=i+1;tree1.add(index[nums[0]]);tree2.add(index[nums[1]]);for(int i=2,sum1,sum2;i<N;++i){sum1=arr1.size()-tree1.count(index[nums[i]]);sum2=arr2.size()-tree2.count(index[nums[i]]);if(sum1>sum2||sum1==sum2&&arr1.size()<=arr2.size()){arr1.emplace_back(nums[i]);tree1.add(index[nums[i]]);}else{arr2.emplace_back(nums[i]);tree2.add(index[nums[i]]);}}arr1.insert(arr1.end(),arr2.begin(),arr2.end());return arr1;}
};

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

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

相关文章

【HarmonyOS4学习笔记】《HarmonyOS4+NEXT星河版入门到企业级实战教程》课程学习笔记(二十)

课程地址&#xff1a; 黑马程序员HarmonyOS4NEXT星河版入门到企业级实战教程&#xff0c;一套精通鸿蒙应用开发 &#xff08;本篇笔记对应课程第 30 节&#xff09; P30《29.数据持久化-用户首选项》 实现数据持久化在harmonyOS中有很多种方式&#xff0c;比较常见的是以下两…

在Redis中使用Lua脚本实现多条命令的原子性操作

Redis作为一个高性能的键值对数据库&#xff0c;被广泛应用于各种场景。然而&#xff0c;在某些情况下&#xff0c;我们需要执行一系列Redis命令&#xff0c;并确保这些命令的原子性。这时&#xff0c;Lua脚本就成为了一个非常实用的解决方案。 问题的提出 假设我们有一个计数…

抠图怎么保存抠出来的部分?这些方法非常简单

图像处理已成为我们日常生活和工作中不可或缺的一部分。无论是设计海报、编辑照片&#xff0c;还是制作视频特效&#xff0c;抠图技术都发挥着至关重要的作用。然而&#xff0c;很多人在完成抠图后&#xff0c;却不知道如何保存抠出来的部分&#xff0c;这无疑给他们的创作带来…

Day63 代码随想录打卡|回溯算法篇---电话号码的字母组合

题目&#xff08;leecode T17&#xff09;&#xff1a; 给定一个仅包含数字 2-9 的字符串&#xff0c;返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下&#xff08;与电话按键相同&#xff09;。注意 1 不对应任何字母。 方法&#xff1a;…

串级PID控制算原理及法详解

文章目录 1. PID 2. 串级PID 3. 串级PID的物理量 4. C语言实现单极PID 5. C语言实现串极PID 6. 模拟仿真 1. PID PID是应用最广泛的闭环控制方法之一&#xff0c;是一种常用的反馈控制方法&#xff0c;对于每个PID控制器由三个部分组成&#xff1a;比例控制&#xff08;…

2024中国西安科博会暨硬科技产业博览会11月召开

2024第18届中国西安国际科学技术产业博览会暨硬科技产业博览会 时间&#xff1a;2024年11月3日-5日 地点&#xff1a;西安国际会展中心 主办单位&#xff1a;中国国际科学技术合作协会 陕西省科技资源统筹中心 协办单位&#xff1a;西安市科学技术协会 西安市中小企业协会、…

Hadoop3:Yarn容量调度器配置多队列案例

一、情景描述 需求1&#xff1a; default队列占总内存的40%&#xff0c;最大资源容量占总资源60%&#xff0c;hive队列占总内存的60%&#xff0c;最大资源容量占总资源80%。 二、多队列优点 &#xff08;1&#xff09;因为担心员工不小心&#xff0c;写递归死循环代码&#…

科研与英文学术论文写作指南——于静老师课程

看到了一个特别棒的科研与英文学术论文写作指南&#xff0c;理论框架实例。主讲人是中科院信息工程研究所的于静老师。推荐理由&#xff1a;写论文和读论文或者讲论文是完全不一样的&#xff0c;即使现在还没有发过论文&#xff0c;但是通过于老师的课程&#xff0c;会给后续再…

Unity之创建与导出PDF

内容将会持续更新&#xff0c;有错误的地方欢迎指正&#xff0c;谢谢! Unity之创建与导出PDF TechX 坚持将创新的科技带给世界&#xff01; 拥有更好的学习体验 —— 不断努力&#xff0c;不断进步&#xff0c;不断探索 TechX —— 心探索、心进取&#xff01; 助力快速…

订单服务-提交订单业务立即购买业务

文章目录 1、提交订单 业务2、在 OrderController 创建 submitOrder 方法3、 在 OrderServiceImpl 中实现 submitOrder 方法4、根据id查询sku详情&#xff08;service-product"&#xff09;5、查询用户地址保存到订单项中&#xff08;service-user&#xff09;6、删除购物…

udp发送数据如果超过1个mtu时,抓包所遇到的问题记录说明

最近在测试Syslog udp发送相关功能&#xff0c;测试环境是centos udp头部的数据长度是2个字节&#xff0c;最大传输长度理论上是65535&#xff0c;除去头部这些字节&#xff0c;可以大概的说是64k。 写了一个超过64k的数据(随便用了一个7w字节的buffer)发送demo&#xff0c;打…

USB-SC-09编程电缆使用手册

USB-SC-09编程电缆是通过电脑的USB口仿真成传统串口&#xff08;俗称COM口&#xff09;&#xff0c;从而使用现有的各种编程软件、通信软件和监控软件等&#xff0c;转换盒上的发光二极管指示数据的收发状态&#xff0c;本电缆适用于三菱FX全系列PLC USB-SC-09电缆外观&#xf…

【AIGC评测体系】大模型评测指标集

大模型评测指标集 &#xff08;☆&#xff09;SuperCLUE&#xff08;1&#xff09;SuperCLUE-V&#xff08;中文原生多模态理解测评基准&#xff09;&#xff08;2&#xff09;SuperCLUE-Auto&#xff08;汽车大模型测评基准&#xff09;&#xff08;3&#xff09;AIGVBench-T2…

【python - 数据】

一、序列 序列&#xff08;sequence&#xff09;是一组有顺序的值的集合&#xff0c;是计算机科学中的一个强大且基本的抽象概念。序列并不是特定内置类型或抽象数据表示的实例&#xff0c;而是一个包含不同类型数据间共享行为的集合。也就是说&#xff0c;序列有很多种类&…

Python数据可视化书籍推荐:利用Python进行数据分析

《利用Python进行数据分析》 这本书几乎是数据分析入门必读书了 主要介绍了python 3个库numpy&#xff08;数组&#xff09;&#xff0c;pandas&#xff08;数据分析&#xff09;和matplotlib&#xff08;绘图&#xff09;的学习 阅读本书可以获得一份关于在Python下操作、处…

2024“国培“来也UiBot6.0 RPA数字机器人开发综合应用

前言 (本博客中会有部分课程ppt截屏,如有侵权请及请及时与小北我取得联系~) 国培笔记: 依次读取数组中每个元素 输出调试信息 [ value=[ "vivian", value[0] "老师", "上午好,O(∩_∩)O哈哈~" ], v…

Ozon、美客多补单测评黑科技:打造无懈可击的自养号补单环境

不管哪个跨境平台的风控都会做升级&#xff0c;相对的补单技术也需要进行相应的做升级&#xff0c;风控升级后&#xff0c;自己养号补单需要注意以下技术问题&#xff0c;以确保补单的稳定性和安全性&#xff1a; 一、物理环境 1. 硬件参数伪装&#xff1a;平台已经开始通过I…

在手机上也能开发软件?而且只需要用几句话就可以自动生成一个应用!

随着人工智能技术的飞速发展&#xff0c;软件开发的门槛正在迅速降低。 曾几何时&#xff0c;开发一款软件需要精通编程语言和掌握复杂的开发工具&#xff0c;而如今&#xff0c;只需几句话的描述&#xff0c;便能在手机上轻松开发出功能齐全的软件。 这一切的背后&#xff0…

Steam夏促怎么注册 Steam夏促账号注册教程

随着夏日的炙热渐渐充斥着每一个角落&#xff0c;Steam平台也赶来添热闹&#xff0c;推出了一系列让人眼前一亮的夏季促销活动。如果你也是游戏爱好者&#xff0c;我们肯定不能错过这次的steam夏促。正直本次夏日促销有着很多的游戏迎来史低和新史低&#xff0c;有各种各样的游…

VSCode里python代码不扩展/级联了的解决办法

如图 解决办法&#xff1a;重新下载新的扩展工具 步骤如下 1、在左边工具栏打开Extensions 2、搜索框输入python&#xff0c;选择别的扩展工具&#xff0c;点击Install - 3在扩展工具所在的目录下&#xff0c;新建一个文件&#xff0c;就可以用了