Leetcode 剑指 Offer II 075.数组的相对排序

题目难度: 简单

原题链接

今天继续更新 Leetcode 的剑指 Offer(专项突击版)系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

给定两个数组,arr1 和 arr2,

  • arr2 中的元素各不相同
  • arr2 中的每个元素都出现在 arr1 中
  • 对 arr1 中的元素进行排序,使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。

示例:

  • 输入:arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
  • 输出:[2,2,2,1,4,3,3,9,6,7,19]

提示:

  • 1 <= arr1.length, arr2.length <= 1000
  • 0 <= arr1[i], arr2[i] <= 1000
  • arr2 中的元素 arr2[i] 各不相同
  • arr2 中的每个元素 arr2[i] 都出现在 arr1 中

题目思考

  1. 如何模拟整个过程?

解决方案

思路
  • 分析题目, 不难发现需要分两部分进行排序:
    1. 对于 arr1 在 arr2 中的数字, 要按照 arr2 的数字出现顺序来排序
    2. 对于 arr1 的其他数字, 需要按照升序排序
  • 我们可以使用一个计数字典统计 arr1 每个数字的出现次数, 然后模拟上述两个过程
  • 首先遍历 arr2 的每个数字, 将 arr1 中所有的该数字作为子数组, 添加到最终结果中
    • 举个例子, 假如 arr2 第一个数字是 5, arr1 的 5 出现了 3 次, 那么就是添加[5,5,5]
    • 而如果该数字没在 arr1 中, 那自然是什么都不添加
    • 另外还需要将该数字从计数字典中移除, 避免重复添加
  • 然后对计数字典的剩余数字按升序排序, 同样将 arr1 中所有的该数字作为子数组, 依次添加到最终结果
  • 上面两步结束后, 得到的数组就是按照上述规则排序后的结果了, 直接返回即可
  • 下面代码中有详细的注释, 方便大家理解
复杂度
  • 时间复杂度 O(N1logN1+N2): 假设 arr1 和 arr2 的元素数目分别是 N1 和 N2, 首先记录 arr1 每个数字的出现次数是 O(N1), 之后遍历 arr2 的复杂度是 O(N2), 最后剩余部分的排序是 O(N1logN1), 综合起来的时间复杂度就是 O(N1logN1+N2)
  • 空间复杂度 O(N1): 使用了额外计数字典存储 arr1 的元素
代码
class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        # 记录arr1每个数字的出现次数
        cnts = collections.Counter(arr1)
        res = []
        for x in arr2:
            # 先按照arr2的顺序依次添加数字
            res += [x] * cnts[x]
            # 注意用过之后要删除
            del cnts[x]
        for x in sorted(cnts):
            # 剩余数字按照升序排列
            res += [x] * cnts[x]
        return res

大家可以在下面这些地方找到我~😊

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊

算法精选 - 微信扫一扫关注我

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Java NIO

1. IO分类概述 1.1 阻塞与非阻塞 阻塞&#xff08;Blocking&#xff09;和非阻塞&#xff08;Nonblocking&#xff09;是在计算机编程中用于描述I/O操作的两个重要概念。阻塞与非阻塞描述的是线程在访问某个资源时&#xff0c;在该资源没有准备就绪期间的处理方式。 1、阻塞&a…

Android使用AlertDialog实现弹出菜单

最近又开始捣鼓APP&#xff0c;许多api , class都忘记怎么用了&#xff0c;楼下使用AlertDialog实现个弹出菜单&#xff0c;结果直接crash&#xff0c;查了半天&#xff0c;终于即将&#xff0c;记录一下…… 1 实现代码 AlertDialog.Builder mBuilder new AlertDialog.Builde…

后端工程师——C++工程师如何准备面试?

相比 Java 语言方向,C++ 入门简单,精通难,找工作竞争压力更小,但 C++ 依然是近年来招聘的热门岗位之一。本文将从以下三个方面进行详细讲解,帮助你对 C++ 相关岗位的就业前景、岗位要求、学习路线等有更充分的了解。 C++工程师面试准备 上两篇文章对 C++ 工程师的招聘需求…

SpringCloud系列(17)--将服务消费者Consumer注册进Zookeeper

前言&#xff1a;在上一章节中我们把服务提供者Provider注册进了Zookeeper&#xff0c;而本章节则是关于如何将服务消费者Consumer注册进Zookeeper 1、再次创建一个服务提供者模块&#xff0c;命名为consumerzk-order80 (1)在父工程下新建模块 (2)选择模块的项目类型为Maven并…

HPE Aruba Networking推出新一代Wi-Fi 7接入点 助力企业高效应对安全、AI与物联网挑战

HPE ArubaNetworking推出的全新Wi-Fi 7接入点&#xff0c;提供全面的AI就绪边缘IT解决方案&#xff0c;旨在为用户和物联网设备提供安全、高性能的连接服务&#xff0c;以实现数据的捕获和路由&#xff0c;从而满足AI训练和推理需求 休斯顿-2024年4月23日-慧与科技(NYSE: HPE)近…

【golang学习之旅】深入理解字符串string数据类型

系列文章 【golang学习之旅】报错&#xff1a;a declared but not used 【golang学习之旅】Go 的基本数据类型 目录 系列文章使用示例string的底层数据结构关于字符串复制字符串是不可变的如何高效的进行字符串拼接&#xff1f; 使用示例 Go 语言中的字符串只是一个只读的字节…

Spring boot + Redis + Spring Cache 实现缓存

学习 Redis 的 value 有 5 种常用的数据结构 Redis 存储的是 key-value 结构的数据。key 是字符串类型&#xff0c;value 有 5 种常用的数据结构&#xff1a; Redis 的图形化工具 Another Redis Desktop Manager Spring Data Redis Redis 的 Java 客户端。 Spring Cache Spr…

AI工具集:解锁智能新境界,一站式解决你的所有需求!

在这个信息爆炸的时代&#xff0c;我们每天都在与大量的数据和信息打交道。如何高效地处理这些信息&#xff0c;提高工作效率和生活品质&#xff0c;成为了我们亟待解决的问题。而AI工具集(AI-321.com)的出现&#xff0c;无疑为我们提供了一把解锁智能新境界的钥匙。 AI-321 | …

VirtualBox7.0.16的蓝屏大坑与ssh登陆ubuntu虚拟机的办法

背景&#xff1a; 安装了最新版的VirtualBox&#xff0c;装了ubuntu系统&#xff0c;在win10下通过ssh死活无法与ubuntu进行正常登陆控制。 然后开始了踩坑。 问题1&#xff1a;ssh登陆失败&#xff0c;但是主机能ping通ubuntu&#xff0c;反过来也能ping通&#xff0c;网络…

地学研究相关工具推荐0426

地学研究相关工具推荐0426 文章目录 地学研究相关工具推荐0426前言工具PanoplyFileZillaGetData Graph DigitizerZotero**谷谷GIS地图下载器** 总结 前言 以下这些工具是之前在进行一些研究过程中使用过的工具&#xff0c;在之后的研究中可能会用到&#xff0c;推荐给大家&…

Unity类银河恶魔城学习记录14-5 p152 Lost currency save and enemy‘s currency drop

Alex教程每一P的教程原代码加上我自己的理解初步理解写的注释&#xff0c;可供学习Alex教程的人参考 此代码仅为较上一P有所改变的代码 【Unity教程】从0编程制作类银河恶魔城游戏_哔哩哔哩_bilibili LostCurrencyController.cs using System.Collections; using System.Colle…

每天五分钟深度学习:如何理解梯度下降算法可以逼近全局最小值?

本文重点 上节课程中,我们已经知道了逻辑回归的代价函数J。要想最小化代价函数,我们需要使用梯度下降算法。 梯度下降算法地直观理解: 为了可视化,我们假设w和b都是单一实数,实际上,w可以是更高地维度。 代价函数J是在水平轴w和b上的曲面,因此曲面的高度就是J(w,b)在…

井字棋游戏

1. 游戏创建 1.1导包 from tkinter import * import numpy as np import math import tkinter.messagebox 1.2 窗口内容 1.2.1创建一个窗口 root Tk() # 窗口名称 root.title("井字棋 from Sun") 1.2.2 创建一个框架&#xff0c;将其放置在窗口中 Frame1 F…

如何进行域名解析?如何清理DNS缓存?(附源码)

目录 1、什么是域名&#xff1f; 2、为什么使用域名&#xff1f; 3、域名解析的完整流程 4、调用gethostbyname系统接口将域名解析成IP地址 5、为什么需要清理系统DNS缓存&#xff1f; 6、使用cmd命令清理DNS缓存 7、通过代码去清除系统DNS缓存 C软件异常排查从入门到精…

图像分类导论:从模型设计到端到端

书籍&#xff1a;An Introduction to Image Classification&#xff1a;From Designed Models to End-to-End Learning 作者&#xff1a;Klaus D. Toennies 出版&#xff1a;Springer Singapore 书籍下载-《图像分类导论》图像分类的传统方法包括在特征空间中进行特征提取和…

怎么提高职场辩论的口才能力的方法

提高职场辩论的口才能力是一个综合而复杂的过程&#xff0c;涉及知识积累、技巧学习、实践锻炼等多个方面。以下是关于如何提高职场辩论口才能力的详细分析和建议。 一、引言 在职场中&#xff0c;良好的口才能力对于个人职业发展具有重要意义。优秀的口才不仅能够提升个人的…

日志分析简单总结

1、分析日志的目的 误报&#xff1a;不是攻击而上报成攻击 漏报&#xff1a;是攻击而没有防御的情况 日志分析可以判断是否误判或者漏判&#xff0c;可以溯源攻击行为 在护网作为防守方必备的技能&#xff08;分析NGAF和态势感知&#xff0c;发现异常&#xff09; 2、攻击出现…

C++进阶--智能指针

智能指针的概念 智能指针是C中的一个重要概念&#xff0c;用于管理动态分配的对象内存。它是一个类模板&#xff0c;通过封装原始指针&#xff0c;并在对象生命周期结束时自动释放内存&#xff0c;从而避免了内存泄漏和资源管理的繁琐工作。 C标准库提供了多种常见的智能指针…

el-date-picker 禁用时分秒选择(包括禁用下拉框展示)

2024.04.26今天我学习了对el-date-picker进行禁用时分秒&#xff0c; 在使用el-date-picker组件的时候&#xff0c;我们有可能遇到需要把时分秒的时间固定&#xff0c;然后并且不能让他修改&#xff1a; 1714120999296 比如右上角的这个时间&#xff0c;我们要给它固定是‘08:…

Open3D(C++) 最小二乘拟合多项式曲线

目录 一、算法原理二、代码实现三、结果展示本文由CSDN点云侠原创,原文链接。如果你不是在点云侠的博客中看到该文章,那么此处便是不要脸的爬虫与GPT。 一、算法原理 多项式曲线表示为: p ( x ) =