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

devtools/2024/9/23 14:36:07/

给你一个下标从 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.ppmy.cn/devtools/57175.html

相关文章

PostgreSQL匹配字符串方法

PostgreSQL匹配字符串方法 在 PostgreSQL 中&#xff0c;如果你想要检查一个包含多个由逗号分隔的值的字符串是否包含特定的子字符串&#xff0c;你可以使用字符串函数来实现这一点。由于你正在查找的是一个由逗号分隔的列表中的特定值&#xff0c;你需要确保在比较时该值不是…

LSTM 简单的案例

后期总结&#xff1a; 参考&#xff1a; [1] 基于 PyTorch LSTM 进行时间序列预测 [2] https://zhuanlan.zhihu.com/p/685266225

Build a Large Language Model (From Scratch)第一章(gpt-4o翻译版)

来源&#xff1a;https://github.com/rasbt/LLMs-from-scratch?tabreadme-ov-file https://www.manning.com/books/build-a-large-language-model-from-scratch

GAMES104:04游戏引擎中的渲染系统1:游戏渲染基础-学习笔记

文章目录 概览&#xff1a;游戏引擎中的渲染系统四个课时概览 一&#xff0c;渲染管线流程二&#xff0c;了解GPUSIMD 和 SIMTGPU 架构CPU到GPU的数据传输GPU性能限制 三&#xff0c;可见性Renderable可渲染对象提高渲染效率Visibility Culling 可见性裁剪 四&#xff0c;纹理压…

数据库测试数据准备厂商 Snaplet 宣布停止运营

上周刚获知「数据库调优厂商 OtterTune 宣布停止运营」。而今天下班前&#xff0c;同事又突然刷到另一家海外数据库工具商 Snaplet 也停止运营了。Snaplet 主要帮助开发团队在数据库中生成仿真度高且合规的测试数据。我们在年初还撰文介绍过它「告别手搓&#xff01;Postgres 一…

linux的安全技术和防火墙

一、安全技术 1.入侵检测系统&#xff1a;特点式不阻断网络访问&#xff0c;主要式提供报警和事后监督&#xff0c;不主动介入&#xff0c;默默的看着你&#xff08;相当于360安全卫士&#xff09; 2.入侵防御系统&#xff1a;透明模式工作&#xff0c;对数据包&#xff0c;网…

phpexcel导入导出

前言&#xff1a; 如果你到处的excel软件打开有问题&#xff0c;下面有介绍解决办法 导入 1. composer init 初始化 2. 下载phpspreadsheet 这里需要注意php版本&#xff0c;需要大于7.2 composer require phpoffice/phpspreadsheet3. 编写代码 <?php require vendo…

Matlab|分时电价环境下用户负荷需求响应分析方法

主要内容 本程序复现《分时电价环境下用户负荷需求响应分析方法》文献中的方法&#xff0c;通过用户对不同时间下用电需求的自弹性和交叉弹性系数分析获得用户需求响应矩阵&#xff0c;进而利用该矩阵对用户在实行基于电价的需求侧管理后的负荷变化情况进行快速分析。 1.1…