Leetcode1122. 数组的相对排序
Every day a Leetcode
题目来源:1122. 数组的相对排序
解法1:哈希
用集合 set 存储 arr2 中的元素。
遍历数组 arr1 ,设当前元素为 num:
- 如果 num 在 set 中出现,用哈希表 hash 记录 num 和它出现的次数。
- 否则,用将 num 插入数组 remain。
遍历数组 arr2,设当前元素为 num。向 ans 中插入 hash[num] 个 num。
将 remain 增序排序,将 remain 插入 ans 的后面。
代码:
/** @lc app=leetcode.cn id=1122 lang=cpp** [1122] 数组的相对排序*/// @lc code=start
class Solution
{
public:vector<int> relativeSortArray(vector<int> &arr1, vector<int> &arr2){unordered_map<int, int> hash;set<int> set(arr2.begin(), arr2.end());vector<int> remain;for (const int &num : arr1){if (set.count(num))hash[num]++;elseremain.push_back(num);}vector<int> ans;for (const int &num : arr2){if (hash.count(num))for (int i = 0; i < hash[num]; i++)ans.push_back(num);}// 未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾sort(remain.begin(), remain.end());for (int i = 0; i < remain.size(); i++)ans.push_back(remain[i]);return ans;}
};
// @lc code=end
结果:

复杂度分析:
时间复杂度:O(mlogm+n),其中 m 和 n 分别是数组 arr1 和 arr2 的长度。构建哈希表的时间复杂度为 O(n),排序的时间复杂度为 O(mlogm)。
空间复杂度:O(logm+n),其中 m 和 n 分别是数组 arr1 和 arr2 的长度。哈希表的空间复杂度为 O(n),排序使用的栈的空间复杂度为 O(mlogm)。
解法2:计数排序
注意到本题中元素的范围为 [0, 1000],这个范围不是很大,我们也可以考虑不基于比较的排序,例如「计数排序」。
优化:实际上,我们不需要使用长度为 1001 的数组,而是可以找出数组 arr1 中的最大值 upper,使用长度为 upper+1 的数组即可。
代码:
/** @lc app=leetcode.cn id=1122 lang=cpp** [1122] 数组的相对排序*/// @lc code=start
// class Solution
// {
// public:
// vector<int> relativeSortArray(vector<int> &arr1, vector<int> &arr2)
// {
// unordered_map<int, int> hash;
// set<int> set(arr2.begin(), arr2.end());
// vector<int> remain;
// for (const int &num : arr1)
// {
// if (set.count(num))
// hash[num]++;
// else
// remain.push_back(num);
// }
// vector<int> ans;
// for (const int &num : arr2)
// {
// if (hash.count(num))
// for (int i = 0; i < hash[num]; i++)
// ans.push_back(num);
// }
// // 未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾
// sort(remain.begin(), remain.end());
// for (int i = 0; i < remain.size(); i++)
// ans.push_back(remain[i]);
// return ans;
// }
// };class Solution
{
public:vector<int> relativeSortArray(vector<int> &arr1, vector<int> &arr2){int upper = *max_element(arr1.begin(), arr1.end());vector<int> freq(upper + 1, 0);for (const int &num : arr1)freq[num]++;vector<int> ans;for (const int &num : arr2){for (int i = 0; i < freq[num]; i++)ans.push_back(num);freq[num] = 0;}for (int num = 0; num <= upper; num++)for (int i = 0; i < freq[num]; i++)ans.push_back(num);return ans;}
};
// @lc code=end
结果:

复杂度分析:
时间复杂度:O(m+n+upper),其中 m 和 n 分别是数组 arr1 和 arr2 的长度。upper 是数组 arr1 的最大值。
空间复杂度:O(upper),其中 upper 是数组 arr1 的最大值。即为数组 freq 需要使用的空间。
相关文章:
Leetcode1122. 数组的相对排序
Every day a Leetcode 题目来源:1122. 数组的相对排序 解法1:哈希 用集合 set 存储 arr2 中的元素。 遍历数组 arr1 ,设当前元素为 num: 如果 num 在 set 中出现,用哈希表 hash 记录 num 和它出现的次数。否则&a…...
CN考研真题知识点二轮归纳(5)
本轮的最后一贴,真题中涉及计网的部分彻底总结完!后期的3轮总结可能会上一些大题,比如路由转发、子网划分什么的,以及重点的背诵内容~ 上期目录: CN考研真题知识点二轮归纳(4)https://jslhyh32…...
windows系统 生成RSA密钥对
在Windows系统上生成密钥对,可以使用多种方法,这里将介绍两种常用的方法: 方法1: 使用PuTTYgen PuTTYgen是PuTTY套件的一部分,是在Windows上生成SSH密钥对的一个流行工具。如果你的目的是SSH密钥对,你可以这样操作&a…...
大文件分片上传并发
我这边使用的是boostrap-fileimput 初始化文件上传框 $(document).ready(function () {$("#file-upload_import").fileinput({uploadUrl: "#",language: "zh", //设置语言showPreview: true,autoReplace: true,// uploadUrl: "/uact/uploa…...
数据结构——基于顺序表实现通讯录
一、. 基于动态顺序表实现通讯录 1.1 功能要求 1)⾄少能够存储100个⼈的通讯信息 2)能够保存⽤⼾信息:名字、性别、年龄、电话、地址等 3)增加联系⼈信息 4)删除指定联系⼈ 5)查找制定联系⼈ 6&…...
行业追踪,2023-11-03
自动复盘 2023-11-03 凡所有相,皆是虚妄。若见诸相非相,即见如来。 k 线图是最好的老师,每天持续发布板块的rps排名,追踪板块,板块来开仓,板块去清仓,丢弃自以为是的想法,板块去留让…...
JSPv2之El
(一)EL的基本语法 1优点 1 jsp的java太长了,el自己的语言${ 开始 }结束 2el直接返回空字符转,而java直接报错 3使用“lt”代替“<”运算符,如果运算符后面是数字,在运算符 *EL取值时,没有数组的下标越界,没有…...
出现 gpg: cancelled by user时的处理方法
今天在使用git commit -S -m "comment" check in 代码的时候, 莫名其妙出现了以下错误: gpg: cancelled by user经过在网上查询资料, 本质原因是GnuPG没有$(tty)的读写权限,有以下两种解决方法是靠谱的: c…...
MySQL中表的增删改查
目录 一、CRUD 二、新增(Create) (1)语法 (2)单行数据全列插入 (3)多行数据指定列插入 三、查询(Retrieve) (1)语法 …...
web.py python服务器两种模板template使用方法
【版权声明】 本文为博主原创文章,未经博主允许严禁转载,我们会定期进行侵权检索。 更多python应用或算法总结请关注我的博客:https://blog.csdn.net/suiyingy,或”乐乐感知学堂“公众号。 web.py是Python Web框架之一,…...
Flutter 01 目录结构入门
一、Flutter目录结构: 二、Flutter入口文件、入口方法: 三、Flutter Demo: demo1: import package:flutter/material.dart;//MaterialApp 和 Scaffold两个组件装饰App void main() {runApp(MaterialApp(home: Scaffold(appBar: A…...
Esxi安装OpenWrt
最近折腾下软路由主要就是实现局域网内的上网。 1.StarWind V2V Converter下载 先去下载个StarWind V2V Converter,觉得麻烦我在网上有找到一个博主的地址点击这里。 这是官网地址传送门,然后一阵乱输入点击下载 然后 双击之后无脑下一步即可。 2.Op…...
tuple 简易实现(C++ 模板元编程)
std::tuple 在标准库里面,tuple主要有下面四个类模板 or 函数模板 tupletuple_sizetuple_elementget 在后续有实现:tuple_size_v tuple_size::value和tuple_element_t tuple_element::type。 事例Example: auto tup std::tuple<in…...
Http代理与socks5代理有何区别?如何选择?(二)
上篇文章我们基本分别了解了http代理与socks5代理的定义与优缺点,接下来我们继续来了解http代理与socks5代理之间的比较与区别。 一、两者的比较 1、功能比较 HTTP代理专门用于Web流量,并在处理HTTP和HTTPS协议方面非常高效。它们可以修改正在传输的数…...
java中main方法和@Test注解的区别
Java的main方法和Test注解在用途和功能上有很大的区别。 main方法是Java应用程序的入口点。当你运行一个Java程序时,JVM会首先查找具有public static void main(String[] args)签名的类,并从这个方法开始执行程序。main方法通常用于控制程序的启动、执行…...
C++进阶语法——STL 标准模板库(下)(Standard Template Library)【学习笔记(七)】
文章目录 STL 代码示例1、迭代器2、算法3、array容器示例4、vector示例5、deque(double ended queue,双端数组)示例6、list(链表)容器7、set示例8、map示例9、stack 示例10、queue示例11、priority_queue (…...
力扣:求最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀,返回空字符串 示例1: 输入: strs ["flower", "flow" , "flight"] 输出: "fl" 示例2: 输入: strs ["dog","racecar","car&…...
Redis入门04-消息通知
目录 Redis中的消息通知 命令行操作 Redis中的管道 Redis中的消息通知 Redis可以用作消息队列的中间件,它提供了一种轻量级、高性能的消息传递机制,适用于实时通信、任务队列、事件处理等各种应用。以下是有关如何使用Redis作为消息队列的一些重要信…...
关于idea使用的一些操作设置
关于idea使用的一些操作设置 1. 常用的一下设置1.1 快捷键相关1.2 配置自动生成注释(类、方法等)1.3 maven项目相关1.4 常见其他的一些操作设置 2. IntelliJ IDEA 取消param注释中参数报错提示3. idea同时打开多个文件,导航栏不隐藏、自动换行…...
CLion 2023.2.2(C ++ IDE智能代码编辑器)
CLion 2023是一款跨平台C/C集成开发环境(IDE)。它为Mac用户提供了高效的编程体验,帮助程序员们在Mac平台上进行C/C开发。 CLion 2023支持多种编译器和调试器,并具有强大的代码分析和导航功能。它还为用户提供了许多便捷的工具和插…...
国防科技大学计算机基础课程笔记02信息编码
1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制,因此这个了16进制的数据既可以翻译成为这个机器码,也可以翻译成为这个国标码,所以这个时候很容易会出现这个歧义的情况; 因此,我们的这个国…...
【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
连锁超市冷库节能解决方案:如何实现超市降本增效
在连锁超市冷库运营中,高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术,实现年省电费15%-60%,且不改动原有装备、安装快捷、…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...
渲染学进阶内容——模型
最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
浪潮交换机配置track检测实现高速公路收费网络主备切换NQA
浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求,本次涉及的主要是收费汇聚交换机的配置,浪潮网络设备在高速项目很少,通…...
Python竞赛环境搭建全攻略
Python环境搭建竞赛技术文章大纲 竞赛背景与意义 竞赛的目的与价值Python在竞赛中的应用场景环境搭建对竞赛效率的影响 竞赛环境需求分析 常见竞赛类型(算法、数据分析、机器学习等)不同竞赛对Python版本及库的要求硬件与操作系统的兼容性问题 Pyth…...
