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

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 题目来源&#xff1a;1122. 数组的相对排序 解法1&#xff1a;哈希 用集合 set 存储 arr2 中的元素。 遍历数组 arr1 &#xff0c;设当前元素为 num&#xff1a; 如果 num 在 set 中出现&#xff0c;用哈希表 hash 记录 num 和它出现的次数。否则&a…...

CN考研真题知识点二轮归纳(5)

本轮的最后一贴&#xff0c;真题中涉及计网的部分彻底总结完&#xff01;后期的3轮总结可能会上一些大题&#xff0c;比如路由转发、子网划分什么的&#xff0c;以及重点的背诵内容~ 上期目录&#xff1a; CN考研真题知识点二轮归纳&#xff08;4&#xff09;https://jslhyh32…...

windows系统 生成RSA密钥对

在Windows系统上生成密钥对&#xff0c;可以使用多种方法&#xff0c;这里将介绍两种常用的方法&#xff1a; 方法1: 使用PuTTYgen PuTTYgen是PuTTY套件的一部分&#xff0c;是在Windows上生成SSH密钥对的一个流行工具。如果你的目的是SSH密钥对&#xff0c;你可以这样操作&a…...

大文件分片上传并发

我这边使用的是boostrap-fileimput 初始化文件上传框 $(document).ready(function () {$("#file-upload_import").fileinput({uploadUrl: "#",language: "zh", //设置语言showPreview: true,autoReplace: true,// uploadUrl: "/uact/uploa…...

数据结构——基于顺序表实现通讯录

一、. 基于动态顺序表实现通讯录 1.1 功能要求 1&#xff09;⾄少能够存储100个⼈的通讯信息 2&#xff09;能够保存⽤⼾信息&#xff1a;名字、性别、年龄、电话、地址等 3&#xff09;增加联系⼈信息 4&#xff09;删除指定联系⼈ 5&#xff09;查找制定联系⼈ 6&…...

行业追踪,2023-11-03

自动复盘 2023-11-03 凡所有相&#xff0c;皆是虚妄。若见诸相非相&#xff0c;即见如来。 k 线图是最好的老师&#xff0c;每天持续发布板块的rps排名&#xff0c;追踪板块&#xff0c;板块来开仓&#xff0c;板块去清仓&#xff0c;丢弃自以为是的想法&#xff0c;板块去留让…...

JSPv2之El

​ (一)EL的基本语法 1优点 1 jsp的java太长了,el自己的语言${ 开始 }结束 2el直接返回空字符转,而java直接报错 3使用“lt”代替“<”运算符&#xff0c;如果运算符后面是数字&#xff0c;在运算符 *EL取值时&#xff0c;没有数组的下标越界&#xff0c;没有…...

出现 gpg: cancelled by user时的处理方法

今天在使用git commit -S -m "comment" check in 代码的时候&#xff0c; 莫名其妙出现了以下错误&#xff1a; gpg: cancelled by user经过在网上查询资料&#xff0c; 本质原因是GnuPG没有$(tty)的读写权限&#xff0c;有以下两种解决方法是靠谱的&#xff1a; c…...

MySQL中表的增删改查

目录 一、CRUD 二、新增&#xff08;Create&#xff09; &#xff08;1&#xff09;语法 &#xff08;2&#xff09;单行数据全列插入 &#xff08;3&#xff09;多行数据指定列插入 三、查询&#xff08;Retrieve&#xff09; &#xff08;1&#xff09;语法 …...

web.py python服务器两种模板template使用方法

【版权声明】 本文为博主原创文章&#xff0c;未经博主允许严禁转载&#xff0c;我们会定期进行侵权检索。 更多python应用或算法总结请关注我的博客&#xff1a;https://blog.csdn.net/suiyingy&#xff0c;或”乐乐感知学堂“公众号。 web.py是Python Web框架之一&#xff0c…...

Flutter 01 目录结构入门

一、Flutter目录结构&#xff1a; 二、Flutter入口文件、入口方法&#xff1a; 三、Flutter Demo&#xff1a; demo1&#xff1a; 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&#xff0c;觉得麻烦我在网上有找到一个博主的地址点击这里。 这是官网地址传送门&#xff0c;然后一阵乱输入点击下载 然后 双击之后无脑下一步即可。 2.Op…...

tuple 简易实现(C++ 模板元编程)

std::tuple 在标准库里面&#xff0c;tuple主要有下面四个类模板 or 函数模板 tupletuple_sizetuple_elementget 在后续有实现&#xff1a;tuple_size_v tuple_size::value和tuple_element_t tuple_element::type。 事例Example&#xff1a; auto tup std::tuple<in…...

Http代理与socks5代理有何区别?如何选择?(二)

上篇文章我们基本分别了解了http代理与socks5代理的定义与优缺点&#xff0c;接下来我们继续来了解http代理与socks5代理之间的比较与区别。 一、两者的比较 1、功能比较 HTTP代理专门用于Web流量&#xff0c;并在处理HTTP和HTTPS协议方面非常高效。它们可以修改正在传输的数…...

java中main方法和@Test注解的区别

Java的main方法和Test注解在用途和功能上有很大的区别。 main方法是Java应用程序的入口点。当你运行一个Java程序时&#xff0c;JVM会首先查找具有public static void main(String[] args)签名的类&#xff0c;并从这个方法开始执行程序。main方法通常用于控制程序的启动、执行…...

C++进阶语法——STL 标准模板库(下)(Standard Template Library)【学习笔记(七)】

文章目录 STL 代码示例1、迭代器2、算法3、array容器示例4、vector示例5、deque&#xff08;double ended queue&#xff0c;双端数组&#xff09;示例6、list&#xff08;链表&#xff09;容器7、set示例8、map示例9、stack 示例10、queue示例11、priority_queue &#xff08;…...

力扣:求最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀&#xff0c;返回空字符串 示例1: 输入: strs ["flower", "flow" , "flight"] 输出: "fl" 示例2: 输入: strs ["dog","racecar","car&…...

Redis入门04-消息通知

目录 Redis中的消息通知 命令行操作 Redis中的管道 Redis中的消息通知 Redis可以用作消息队列的中间件&#xff0c;它提供了一种轻量级、高性能的消息传递机制&#xff0c;适用于实时通信、任务队列、事件处理等各种应用。以下是有关如何使用Redis作为消息队列的一些重要信…...

关于idea使用的一些操作设置

关于idea使用的一些操作设置 1. 常用的一下设置1.1 快捷键相关1.2 配置自动生成注释&#xff08;类、方法等&#xff09;1.3 maven项目相关1.4 常见其他的一些操作设置 2. IntelliJ IDEA 取消param注释中参数报错提示3. idea同时打开多个文件&#xff0c;导航栏不隐藏、自动换行…...

CLion 2023.2.2(C ++ IDE智能代码编辑器)

CLion 2023是一款跨平台C/C集成开发环境&#xff08;IDE&#xff09;。它为Mac用户提供了高效的编程体验&#xff0c;帮助程序员们在Mac平台上进行C/C开发。 CLion 2023支持多种编译器和调试器&#xff0c;并具有强大的代码分析和导航功能。它还为用户提供了许多便捷的工具和插…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)

引言 工欲善其事&#xff0c;必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后&#xff0c;我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集&#xff0c;就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...