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

3072. 将元素分配到两个数组中 II Rust 线段树 + 离散化

题目

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

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

你需要使用 n 次操作,将 nums 的所有元素分配到两个数组 arr1arr2 中。在第一次操作中,将 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
连接数组 arr1arr2 形成数组 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

思路

离散化 + 线段树,由于基础的线段树可以AC,不再使用懒标记去优化。

AC代码

use std::collections::HashMap;struct Tree{tree: Vec<i32>
}impl Tree {pub fn new(len: usize) -> Self {Tree {tree: vec![0; len]}}/*** 更新**/pub fn update(&mut self, node: usize, sign_idx: usize, l: usize, r: usize) {if l == r {self.tree[node] += 1;return;}let mid: usize = l + r >> 1;let l_node: usize = (node << 1) + 1;let r_node: usize = l_node + 1;if sign_idx <= mid {self.update(l_node, sign_idx, l, mid);} else {self.update(r_node, sign_idx, mid + 1, r);}self.tree[node] = self.tree[l_node] + self.tree[r_node];}/*** 查询**/pub fn query(&mut self, node: usize, l: usize, r: usize, start: usize, end: usize) -> i32 {if l > end || r < start {return 0;}if l >= start && r <= end {return self.tree[node];}let mid: usize = l + r >> 1;let l_node: usize = (node << 1) + 1;let r_node: usize = l_node + 1;self.query(l_node, l, mid, start, end) + self.query(r_node, mid + 1, r, start, end)}
}impl Solution {pub fn result_array(v: Vec<i32>) -> Vec<i32> {let len: usize = v.len();let tree_len: usize = len << 2;let mut tree1: Tree = Tree::new(tree_len);let mut tree2: Tree = Tree::new(tree_len);let mut arr1: Vec<i32> = vec![v[0]];let mut arr2: Vec<i32> = vec![v[1]];let mut mp: HashMap<usize, usize> = HashMap::new();let mut cp_v: Vec<i32> = v.clone();cp_v.sort();for (idx, tem) in cp_v.iter().enumerate() {mp.insert(*tem as usize, idx);}if let Some(tem_val) = mp.get(&(v[0] as usize)) {tree1.update(0, *tem_val, 0, len - 1);}if let Some(tem_val) = mp.get(&(v[1] as usize)) {tree2.update(0, *tem_val, 0, len - 1);}for idx in 2 .. len {let val: i32 = v[idx];let mut mp_val: usize = 0;if let Some(tem_val) = mp.get(&(val as usize)) {mp_val = *tem_val;}            let s1: i32 = tree1.query(0, 0, len - 1, mp_val + 1, len - 1);let s2: i32 = tree2.query(0, 0, len - 1, mp_val + 1, len - 1);if s1 > s2 {arr1.push(val);tree1.update(0, mp_val, 0, len - 1);continue;}if s2 > s1 {arr2.push(val);tree2.update(0, mp_val, 0, len - 1);continue;}let len1: usize =  arr1.len();let len2: usize = arr2.len();if len1 <= len2 {arr1.push(val);tree1.update(0, mp_val, 0, len - 1);} else {arr2.push(val);tree2.update(0, mp_val, 0, len - 1);}}arr1.extend(arr2);arr1}
}

推荐几款学习编程的免费平台

免费在线开发平台(https://docs.ltpp.vip/LTPP/)

       探索编程世界的新天地,为学生和开发者精心打造的编程平台,现已盛大开启!这个平台汇集了近4000道精心设计的编程题目,覆盖了C、C++、JavaScript、TypeScript、Go、Rust、PHP、Java、Ruby、Python3以及C#等众多编程语言,为您的编程学习之旅提供了一个全面而丰富的实践环境。       
      在这里,您不仅可以查看自己的代码记录,还能轻松地在云端保存和运行代码,让编程变得更加便捷。平台还提供了私聊和群聊功能,让您可以与同行们无障碍交流,分享文件,共同进步。不仅如此,您还可以通过阅读文章、参与问答板块和在线商店,进一步拓展您的知识边界。
       为了提升您的编程技能,平台还设有每日一题、精选题单以及激动人心的编程竞赛,这些都是备考编程考试的绝佳资源。更令人兴奋的是,您还可以自定义系统UI,选择视频或图片作为背景,打造一个完全个性化的编码环境,让您的编程之旅既有趣又充满挑战。

免费公益服务器(https://docs.ltpp.vip/LTPP-SHARE/linux.html)

       作为开发者或学生,您是否经常因为搭建和维护编程环境而感到头疼?现在,您不必再为此烦恼,因为一款全新的免费公共服务器已经为您解决了所有问题。这款服务器内置了多种编程语言的编程环境,并且配备了功能强大的在线版VS Code,让您可以随时随地在线编写代码,无需进行任何复杂的配置。
随时随地,云端编码
       无论您身在何处,只要有网络连接,就可以通过浏览器访问这款公共服务器,开始您的编程之旅。这种云端编码的便利性,让您的学习或开发工作不再受限于特定的设备或环境。
丰富的编程语言支持
       服务器支持包括C、C++、JavaScript、TypeScript、Go、Rust、PHP、Java、Ruby、Python3以及C#等在内的多种主流编程语言,满足不同开发者和学生的需求。无论您是初学者还是资深开发者,都能找到适合自己的编程环境。
在线版VS Code,高效开发
       内置的在线版VS Code提供了与本地VS Code相似的编辑体验,包括代码高亮、智能提示、代码调试等功能,让您即使在云端也能享受到高效的开发体验。
数据隐私和安全提醒
       虽然服务器是免费的,但为了保护您的数据隐私和安全,我们建议您不要上传任何敏感或重要的数据。这款服务器更适合用于学习和实验,而非存储重要信息。

免费公益MYSQL(https://docs.ltpp.vip/LTPP-SHARE/mysql.html)

       作为一名开发者或学生,数据库环境的搭建和维护往往是一个复杂且耗时的过程。但不用担心,现在有一款免费的MySQL服务器,专为解决您的烦恼而设计,让数据库的使用变得简单而高效。
性能卓越,满足需求
       虽然它是免费的,但性能绝不打折。服务器提供了稳定且高效的数据库服务,能够满足大多数开发和学习场景的需求。
在线phpMyAdmin,管理更便捷
       内置的在线phpMyAdmin管理面板,提供了一个直观且功能强大的用户界面,让您可以轻松地查看、编辑和管理数据库。
数据隐私提醒,安全第一
       正如您所知,这是一项公共资源,因此我们强烈建议不要上传任何敏感或重要的数据。请将此服务器仅用于学习和实验目的,以确保您的数据安全。

免费在线WEB代码编辑器(https://docs.ltpp.vip/LTPP-WEB-IDE/)

       无论你是开发者还是学生,编程环境的搭建和管理可能会占用你宝贵的时间和精力。现在,有一款强大的免费在线代码编辑器,支持多种编程语言,让您可以随时随地编写和运行代码,提升编程效率,专注于创意和开发。
多语言支持,无缝切换
       这款在线代码编辑器支持包括C、C++、JavaScript、TypeScript、Go、Rust、PHP、Java、Ruby、Python3以及C#在内的多种编程语言,无论您的项目需要哪种语言,都能在这里找到支持。
在线运行,快速定位问题
       您可以在编写代码的同时,即时运行并查看结果,快速定位并解决问题,提高开发效率。
代码高亮与智能提示
       编辑器提供代码高亮和智能提示功能,帮助您更快地编写代码,减少错误,提升编码质量。

免费二维码生成器(https://docs.ltpp.vip/LTPP-QRCODE/)

       二维码(QR Code)是一种二维条码,能够存储更多信息,并且可以通过智能手机等设备快速扫描识别。它广泛应用于各种场景,如:
企业宣传
       企业可以通过二维码分享公司网站、产品信息、服务介绍等。
活动推广
       活动组织者可以创建二维码,参与者扫描后可以直接访问活动详情、报名链接或获取电子门票。
个人信息分享
       个人可以生成包含联系方式、社交媒体链接、个人简历等信息的二维码。
电子商务
       商家使用二维码进行商品追踪、促销活动、在线支付等。
教育
       教师可以创建二维码,学生扫描后可以直接访问学习资料或在线课程。
交通出行
       二维码用于公共交通的票务系统,乘客扫描二维码即可进出站或支付车费。        功能强大的二维码生成器通常具备用户界面友好,操作简单,即使是初学者也能快速上手和生成的二维码可以在各种设备和操作系统上扫描识别的特点。

相关文章:

3072. 将元素分配到两个数组中 II Rust 线段树 + 离散化

题目 给你一个下标从 1 开始、长度为 n 的整数数组 nums 。 现定义函数 greaterCount &#xff0c;使得 greaterCount(arr, val) 返回数组 arr 中 严格大于 val 的元素数量。 你需要使用 n 次操作&#xff0c;将 nums 的所有元素分配到两个数组 arr1 和 arr2 中。在第一次操…...

day35|1005.K次取反后最大化的数组和 134. 加油站135. 分发糖果

文章目录 python语法记录 sort格式 1005.K次取反后最大化的数组和思路方法一方法二 按照绝对值排序 教程&#x1f388;✨ 背住 按照绝对值进行降序排序的语法是&#xff1a; 134. 加油站思路方法一 教程解法方法二 暴力求解 135. 分发糖果思路方法一 总结 python语法记录 sort …...

HWA和BSS区别

芯片中的HWA&#xff08;Hardware Accelerator&#xff09;模块功能主要是为了加速雷达信号处理的特定任务。HWA模块在雷达系统中起到关键作用&#xff0c;以下是其主要功能和作用&#xff1a; 信号预处理&#xff1a; 滤波&#xff1a;对接收到的雷达信号进行滤波&#xff0c;…...

【Excel】Excel中将日期格式转换为文本格式,并按日期显示。

【问题需求】 在使用excel进行数据导入的过程中&#xff0c; 有的软件要求日期列必须是文本格式。 但是直接将日期列的格式改为文本后&#xff0c;显示一串数字&#xff0c;而不按日期显示。 进而无法导入使用。 【解决方法】 使用【TXET】函数公式进行处理&#xff0c; 在单…...

物联网学习小记

https://www.cnblogs.com/senior-engineer/p/10045658.html GOSP: 提供类似Qt的API接口&#xff0c;仅需要几百KB的硬件资源&#xff08;比Qt小的多&#xff09;&#xff0c;能运行在Qt不支持的低配置硬件上&#xff08;对Qt生态形成补充&#xff09;&#xff0c;适用于嵌入式…...

代码随想录-Day29

491. 非递减子序列 给你一个整数数组 nums &#xff0c;找出并返回所有该数组中不同的递增子序列&#xff0c;递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。 数组中可能含有重复元素&#xff0c;如出现两个整数相等&#xff0c;也可以视作递增序列的一种特殊情…...

C/C++ 进阶(6)红黑树

个人主页&#xff1a;仍有未知等待探索-CSDN博客 专题分栏&#xff1a;C 目录 一、概念 性质 二、操作 插入 情况一&#xff1a;cur为红、p为红、g为黑&#xff0c;如果u存在且为红 步骤&#xff1a; 情况二&#xff1a;cur为红、p为红、g为黑&#xff0c;如果u不存在或…...

【Vue】构建vuex-cart模块

说明&#xff1a;既然明确数据要存 vuex&#xff0c;建议分模块存&#xff0c;购物车数据存 cart 模块&#xff0c;将来还会有 user 模块&#xff0c;article 模块… 新建 store/modules/cart.js 挂载到 vuex 仓库上 store/cart.js import Vue from vue import Vuex from vu…...

如何成为嵌入式系统工程师?

各位朋友&#xff0c;如果你们有意向投身于嵌入式开发领域&#xff0c;那么强烈建议你们在软件和硬件两个方面均展开深入且全面的学习。 嵌入式计算机作为嵌入式系统的核心技术支撑&#xff0c;其是直接面向用户、产品以及应用的&#xff0c;无论是软件还是硬件方面都能发挥重要…...

【AI大模型】Transformers大模型库(七):单机多卡推理之device_map

目录​​​​​​​ 一、引言 二、单机多卡推理之device_map 2.1 概述 2.2 自动配置&#xff0c;如device_map"auto" 2.3 手动配置&#xff0c;如device_map"cuda:1" 三、总结 一、引言 这里的Transformers指的是huggingface开发的大模型库&#x…...

驱动代码编写(一)

驱动程序的作用 驱动程序是指与硬件设备和操作系统进行通信的软件。它的主要功能有以下几个方面&#xff1a; 提供硬件支持&#xff1a;驱动程序允许操作系统与硬件设备进行通信&#xff0c;以便正确地操作和控制硬件设备。它可以向操作系统提供有关硬件设备的各种信息&#x…...

Prompt-to-Prompt Image Editing with Cross Attention Control

Prompt-to-Prompt Image Editing with Cross Attention Control (P2P) Amir Hertz, Tel Aviv University, ICLR23, Paper, Code 1. 前言 编辑对这些生成模型来说是具有挑战性的&#xff0c;因为编辑技术的一个固有特性是保留大部分原始图像&#xff0c;而在基于文本的模型中…...

实验11 OSPF协议配置

实验11 OSPF协议配置 一、OSPF单区域配置&#xff08;一&#xff09;原理描述&#xff08;二&#xff09;实验目的&#xff08;三&#xff09;实验内容&#xff08;四&#xff09;实验配置&#xff08;五&#xff09;实验步骤 二、OSPF多区域配置&#xff08;一&#xff09;原理…...

ChatGPT-4o, 腾讯元宝,通义千问对比测试中文文化

国内的大模型应用我选择了国内综合实力最强的两个&#xff0c;一个是腾讯元宝&#xff0c;一个是通义千问。其它的豆包&#xff0c;Kimi&#xff0c;文心一言等在某些领域也有强于竞品的表现。 问一个中文文化比较基础的问题,我满以为中文文化chatGPT不如国内的大模型。可事实…...

node.js学习

node.js学习实操及笔记 温故node.js&#xff0c;node.js学习实操过程及笔记~ node.js学习视频node.js官网node.js中文网实操笔记githubcsdn笔记 为什么学node.js 可以让别人访问我们编写的网页为后续的框架学习打下基础&#xff0c;三大框架vue react angular离不开node.js …...

python将一个图片雕刻镂空成二维码

本文使用创作助手。 要将一个图片雕刻镂空成二维码&#xff0c;你可以使用Python中的Pillow库来处理图像&#xff0c;并使用qrcode库来生成二维码。以下是一个示例代码&#xff0c;用于将图片雕刻镂空成二维码&#xff1a; import qrcode from PIL import Image# 打开待处理的…...

OS进程取样器OS Process Sampler执行CMD/Shell命令

Apache JMeter - Users Manual: Component Reference 1.背景 项目上最近需要测试一种很少用到的DICOM协议,但是网上资料很少,基本上可以总结为三种方案: 直接发送TCP 16进制数据包,但是参数化数据准备难度大通过开发封装jar包发送,需要开发组提供通过发送cmd命令给前置机…...

excel两个数据表格,怎样实现筛选的联动?

如图&#xff0c;想要通过处理器或者像素条件进行筛选&#xff0c;形成一个右边图2的对比表&#xff0c;如何实现实现联动显示呢&#xff1f; 这个在excel里可以借用数据透视表切片器来完成。步骤如下&#xff1a; 1.添加表 选中数据区域中任意一个单元格&#xff0c;点击 插…...

python,django好的get和post请求

获得get请求 df request.GET.get("dades")获得post请求 文件settings.py关闭csrf MIDDLEWARE [ ‘django.middleware.security.SecurityMiddleware’, ‘django.contrib.sessions.middleware.SessionMiddleware’, ‘django.middleware.common.CommonMiddleware’…...

volatile的用法

目录 前言 使用volatile的注意事项&#xff1a; 示例&#xff1a; 总结&#xff1a; 前言 在嵌入式C编程中&#xff0c;volatile是一个关键字&#xff0c;它用于告知编译器被修饰的变量可能会在程序的任何地方、任何时候被不可预见的、非程序本身控制的因素所改变。这通常…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

【git】把本地更改提交远程新分支feature_g

创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)

引言 在人工智能飞速发展的今天&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为技术领域的焦点。从智能写作到代码生成&#xff0c;LLM 的应用场景不断扩展&#xff0c;深刻改变了我们的工作和生活方式。然而&#xff0c;理解这些模型的内部…...

从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践

作者&#xff1a;吴岐诗&#xff0c;杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言&#xff1a;融合数据湖与数仓的创新之路 在数字金融时代&#xff0c;数据已成为金融机构的核心竞争力。杭银消费金…...

PostgreSQL——环境搭建

一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在&#xff0…...