【Leetcode】3159. 查询数组中元素的出现位置
文章目录
- 题目
- 思路
- 代码
- 复杂度分析
- 时间复杂度
- 空间复杂度
- 结果
- 总结
题目
题目链接🔗
给你一个整数数组 nums ,一个整数数组 queries 和一个整数 x 。
对于每个查询 q u e r i e s [ i ] queries[i] queries[i] ,你需要找到 n u m s nums nums 中第 q u e r i e s [ i ] queries[i] queries[i] 个 x x x 的位置,并返回它的下标。如果数组中 x x x 的出现次数少于 q u e r i e s [ i ] queries[i] queries[i] ,该查询的答案为 − 1 -1 −1 。
请你返回一个整数数组 a n s w e r answer answer ,包含所有查询的答案。
示例 1:
输入:nums = [1,3,1,7], queries = [1,3,2,4], x = 1
输出:[0,-1,2,-1]
解释:
第 1 个查询,第一个 1 出现在下标 0 处。 第 2 个查询,nums 中只有两个 1 ,所以答案为 -1 。 第 3 个查询,第二个
1 出现在下标 2 处。 第 4 个查询,nums 中只有两个 1 ,所以答案为 -1 。
示例 2:
输入:nums = [1,2,3], queries = [10], x = 5
输出:[-1]
解释:
第 1 个查询,nums 中没有 5 ,所以答案为 -1 。
提示:
- 1 ≤ n u m s . l e n g t h , q u e r i e s . l e n g t h ≤ 1 0 5 1 \leq nums.length, queries.length \leq 10^5 1≤nums.length,queries.length≤105
- 1 ≤ q u e r i e s [ i ] ≤ 1 0 5 1 \leq queries[i] \leq 10^5 1≤queries[i]≤105
- 1 ≤ n u m s [ i ] , x ≤ 1 0 4 1 \leq nums[i], x \leq 10^4 1≤nums[i],x≤104
思路
-
处理查询之前的预处理:
为了能快速回答每个查询,我们可以预先遍历数组 n u m s nums nums,记录所有出现 x x x 的下标。将所有这些下标存储在一个数组 a r r arr arr 中。 -
处理每个查询:
对于每个查询 q u e r i e s [ i ] queries[i] queries[i],如果 q u e r i e s [ i ] queries[i] queries[i] 大于数组 a r r arr arr 的长度,则返回 − 1 -1 −1,表示没有足够的 x x x 出现。否则返回 a r r [ q u e r i e s [ i ] − 1 ] arr[queries[i] - 1] arr[queries[i]−1],即第 q u e r i e s [ i ] queries[i] queries[i] 个 x x x 的下标。
代码
class Solution {
public:vector<int> occurrencesOfElement(vector<int>& nums, vector<int>& queries, int x) {vector<int> arr;vector<int> answer;for(int i = 0; i < nums.size(); ++i){if(nums[i] == x){arr.push_back(i);}}for(int i = 0; i < queries.size(); ++i){if(queries[i] > arr.size())answer.push_back(-1);else answer.push_back(arr[queries[i]-1]);}return answer;}
};
复杂度分析
时间复杂度
-
预处理部分:
我们遍历 n u m s nums nums 一次,寻找所有出现 x x x 的位置,时间复杂度为 O ( n ) O(n) O(n),其中 n n n 是数组 n u m s nums nums 的长度。 -
查询部分:
对于每个查询,我们访问 a r r arr arr 数组,查找第 q u e r i e s [ i ] queries[i] queries[i] 个 x x x 的下标,这个操作的时间复杂度为 O ( 1 ) O(1) O(1)。因此,处理所有查询的时间复杂度是 O ( q ) O(q) O(q),其中 q q q 是查询数组 q u e r i e s queries queries 的长度。
总时间复杂度为 O ( n + q ) O(n + q) O(n+q),其中 n n n 是 n u m s nums nums 数组的长度, q q q 是查询数组 q u e r i e s queries queries 的长度。
空间复杂度
额外使用了一个数组 a r r arr arr 来存储 x x x 的所有下标,空间复杂度是 O ( n ) O(n) O(n),其中 n n n 是 n u m s nums nums 数组的长度。
结果
总结
通过预处理来加速查询,先遍历一遍 n u m s nums nums 数组,找出所有 x x x 出现的位置,然后对每个查询进行常数时间的处理
相关文章:
【Leetcode】3159. 查询数组中元素的出现位置
文章目录 题目思路代码复杂度分析时间复杂度空间复杂度 结果总结 题目 题目链接🔗 给你一个整数数组 nums ,一个整数数组 queries 和一个整数 x 。 对于每个查询 q u e r i e s [ i ] queries[i] queries[i] ,你需要找到 n u m s nums nu…...
PHP语言laravel框架中基于Redis的异步队列使用实践与原理
在 Laravel 中,基于 Redis 的异步队列是通过 Laravel 的队列系统与 Redis 服务结合来实现的。这种队列机制允许你将任务推送到队列中,并由后台工作进程异步处理这些任务。这样,你就可以将耗时的操作(如发送邮件、处理视频、数据同…...
Element-plus自动导入
安装 npm i element-plus 自动引入 1. 安装两个插件 npm install -D unplugin-vue-components unplugin-auto-import2. 配置插件 vue3项目修改vite.config.js,把两个插件添加入即可,注意:不是覆盖原有配置 Vite // vite.config.js import { define…...
贪心算法(常见贪心模型)
常见贪心模型 简单排序模型 最小化战斗力差距 题目分析: #include <bits/stdc.h> using namespace std;const int N 1e5 10;int n; int a[N];int main() {// 请在此输入您的代码cin >> n;for (int i 1;i < n;i) cin >> a[i];sort(a1,a1n);…...
碰一碰发视频后端源码技术开发详解,支持OEM
一、引言 碰一碰发视频作为一种新颖的交互方式,在前端为用户带来便捷体验的同时,后端技术起着至关重要的支撑作用。后端负责管理视频资源、处理 NFC 标签信息与视频的关联逻辑、用户数据的存储与分析以及与前端的高效通信,确保整个系统稳定、…...
Python vs PHP:哪种语言更适合网页抓取
本文将比较 Python 和 PHP,以帮助读者确定哪种语言更适合他们的需求。文章将探讨两种语言的优点和缺点,并根据读者的经验水平分析哪种语言可能更容易上手。接下来,文章将深入探讨哪种语言在抓取网页数据方面更胜一筹。 简而言之,…...
SpringBoot 新特性
优质博文:IT-BLOG-CN 2.1.0新特性最低支持jdk8,支持tomcat9 对响应式编程的支持,spring-boot-starter-webflux starter POM可以快速开始使用Spring WebFlux,它由嵌入式Netty服务器支持 1.5.8 2.1.0/2.7.0/3.0.0 Configuration propertie…...
NAT 技术如何解决 IP 地址短缺问题?
NAT 技术如何解决 IP 地址短缺问题? 前言 这是我在这个网站整理的笔记,有错误的地方请指出,关注我,接下来还会持续更新。 作者:神的孩子都在歌唱 随着互联网的普及和发展,IP 地址的需求量迅速增加。尤其是 IPv4 地址&…...
微积分复习(微分方程)
1,一阶微分方程 可分离的微分方程: 可以把x和y分列等号两边,然后求积分可以解决 齐次方程和准齐次方程 要求是 :yf(y/x),也就是没有单独的x项,我们可以通过设ty/x来统一变量方便我们运算 准齐次方程就是常数项不统一,我们可以将Xxa,Yyb来消灭常数项进而转化为齐次形式…...
动态规划子序列问题系列一>等差序列划分II
题目: 解析: 1.状态表示: 2.状态转移方程: 这里注意有个优化 3.初始化: 4.填表顺序: 5.返回值: 返回dp表总和 代码: public int numberOfArithmeticSlices(int[] nums) {in…...
【连续学习之SSL算法】2018年论文Selfless sequential learning
1 介绍 年份:2018 期刊: arXiv preprint Aljundi R, Rohrbach M, Tuytelaars T. Selfless sequential learning[J]. arXiv preprint arXiv:1806.05421, 2018. 本文提出了一种名为SLNID(Sparse coding through Local Neural Inhibition and…...
【FastAPI】中间件
【FastAPI】中间件 一、概述二、作用2.1 日志记录与监控2.2 身份验证与授权2.3 CORS(跨域资源共享)2.4 Gzip压缩2.5 会话管理2.6 自定义功能2.7 执行顺序 三、 总结四、相关链接 一、概述 FastAPI的中间件提供了一种强大的机制,允许开发者在…...
文档大师:打造一站式 Word 报告解决方案1
前言 在政府、医院、银行、财务以及销售等领域,常常需要创建各种报告文件来展开工作汇报,譬如季度销售报告、年度总结报告、体检报告和保险合同等。在没有报表工具支持之前,这类报告主要通过 Word 制作,费时费力且难以维护&#…...
再谈c++线性关系求值
目的 线性关系是最简单的一种关系,在编程当中应用非常多,所以,再说一次线性关系。 线性关系的定义是这样的: 两个变量之间存在一次方函数关系,就称它们之间存在线性关系。正比例关系是线性关系中的特例,反…...
【ES6复习笔记】Class类(15)
介绍 ES6 提供了更接近传统语言的写法,引入了 Class(类)这个概念,作为对象的模板。通过 class 关键字,可以定义类。基本上,ES6 的 class 可以看作只是一个语法糖,它的绝大部分功能,…...
AppAgent 源码 (xml 解析)
1. 数据准备 adb shell uiautomator dump /sdcard/output.xml # 获取手机ui界面的xml文件 adb pull /sdcard/output.xml output.xml # 将手机上的xml文件拉取到电脑上具体的xml文件: <?xml version1.0 encodingUTF-8 standaloneyes ?> <hierarchy ro…...
Oracle 11G还有新BUG?ORACLE 表空间迷案!
前段时间遇到一个奇葩的问题,在开了SR和oracle support追踪两周以后才算是有了不算完美的结果,在这里整理出来给大家分享。 1.问题描述 12/13我司某基地MES全厂停线,系统卡死不可用,通知到我排查,查看alert log看到是…...
FreeSwitch中启用WebRTC
在FreeSwitch中启用WebRTC需要进行一系列配置。以下是详细的步骤: 1. 安装必要的依赖: 确保安装了支持WebRTC的依赖库,如libsrtp。 2. 配置SIP Profile: 编辑 conf/sip_profiles/internal.xml 文件,添加或修改以下内…...
力扣矩阵-算法模版总结
lc-73.矩阵置零-(时隔14天)-12.27 思路:(23min22s) 1.直接遍历遇0将行列设0肯定不行,会影响后续判断,题目又要求原地算法,那么进一步考虑是否可以将元素为0,其行列需要设为0的位置给存储下来,最后再遍历根据…...
服务端高并发分布式结构演进之路
个人主页:C忠实粉丝 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C忠实粉丝 原创 服务端高并发分布式结构演进之路 收录于专栏[redis] 本专栏旨在分享学习Redis的一点学习笔记,欢迎大家在评论区交流讨论💌 目录 概述 …...
虚拟机桥接模式
主机Win10,虚拟机xp 1.虚拟机设置中选择桥接模式 2.在虚拟机菜单:编辑>虚拟机网络编辑,点击“更改设置”,可以看到三个网卡,这三个网卡分别对应不同的网络共享模式。桥接模式须使用VMnet0,如果没看到这个网卡&…...
JVM调优实践篇
理论篇 1多功能养鱼塘-JVM内存 大鱼塘O(可分配内存): JVM可以调度使用的总的内存数,这个数量受操作系统进程寻址范围、系统虚拟内存总数、系统物理内存总数、其他系统运行所占用的内存资源等因素的制约。 小池塘A&a…...
SpeedTree学习笔记总结
SpeedTree是一款业界领先的三维树木植被建模软件,特别适用于游戏开发和影视制作。 一、基础操作 旋转:鼠标左键 平移:鼠标中键 缩放:鼠标中键滚动 Trunks树干节点 Branches树枝 Cap给树干封口 Frond创建大树叶 Decorations…...
【MuJoCo和PhysX】
MuJoCo 与 Unity 的 PhysX 引擎的主要区别 应用领域: MuJoCo:主要用于机器人学、强化学习、生物力学等领域,擅长处理多自由度、复杂动力学问题,尤其适合进行高精度的物理仿真。 Unity PhysX:主要用于游戏开发、虚拟现…...
HTML制作一个普通的背景换肤案例2024版
一,完整的代码: <!DOCTYPE html> <html lang"zh"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>换肤</t…...
python学opencv|读取图像(二十一)使用cv2.circle()绘制圆形进阶
【1】引言 前序已经掌握了使用cv2.circle()绘制圆形的基本操作,相关链接为: python学opencv|读取图像(二十)使用cv2.circle()绘制圆形-CSDN博客 由于圆形本身绘制起来比较简单,因此可以自由操作的空间也就大&#x…...
qt QZipReader详解
1、概述 QZipReader 是 Qt 中用于从 .zip 文件中读取和提取文件内容的类。它提供了便捷的方法来访问压缩包中的文件和目录,并允许你解压缩单个或多个文件。通过 QZipReader,你可以以编程方式读取 .zip 文件中的内容,并提取它们到目标目录中。…...
开发场景中Java 集合的最佳选择
在 Java 开发中,集合类是处理数据的核心工具。合理选择集合,不仅可以提高代码效率,还能让代码更简洁。本篇文章将重点探讨 List、Set 和 Map 的适用场景及优缺点,帮助你在实际开发中找到最佳解决方案。 一、List:有序存…...
顶顶通呼叫中心中间件mod_cti模块安全增强,预防盗打风险(mod_cti基于FreeSWITCH)
文章目录 前言联系我们mod_cti版本支持安全加强说明 前言 FreeSWITCH暴露在公网最大的风险就是被不法之人盗打 出现盗打的主要原因以下几点: 分机密码太简单或者密码泄露了拨号方案配置不合理sofia配置错误 所以我们给顶顶通呼叫中心中间件添加了安全加强功能&am…...
bash shell的条件语句
~ script% touch if.sh ~ script% chmod 755 if.sh1.if-then-fi #!/usr/bin/env bashFOOD$1 if [ $FOOD"apple" ] thenecho The food is $FOOD fi exit 0~ script % ./if.sh apple The food is apple如果要将多条语句写在一行,可以…...
拦截器Interceptor与过滤器Filter
拦截器Interceptor 定义: SpringMVC内置拦截机制,允许在请求被目标方法处理的前后进行拦截,执行一些额外操作;比如:权限验证,日志记录,数据共享等。 实现步骤 1、自定义拦截器 Component public class …...
水电站视频智能监控系统方案设计与技术应用方案
一、背景需求 水电站作为国家重要的能源基地,其安全运行对于保障能源供应和社会稳定具有重要意义。然而,传统的人工监控方式存在着诸多问题,如人力成本高、监控范围有限、反应不及时等。因此,水电站急需引进一种先进的视频智能监控…...
教师管理系统
大概功能: 1.显示所有教师 2.按姓名查找教师 3.按工号查找教师 4.增加教师 5.删除教师 6.退出 数据会保存到 txt 文件里面 姓名:必须是中文 手机号码:必须是11位,必须是数字 效果展示: 代码展示: Teache…...
nexus docker安装
#nexus docker 安装 docker pull sonatype/nexus3 mkdir -p /data/nexus-data docker run -itd -p 8081:8081 --privilegedtrue --name nexus3 \ -v /data/nexus-data:/var/nexus-data --restartalways docker.io/sonatype/nexus3 #访问 http://192.168.31.109:8081/ 用户名&am…...
canvas之进度条
canvas之进度条 效果: 封装的组件 <template><div class"circle" :style"{ width: props.radius px, height: props.radius px }"><div class"circle-bg" :style"{ width: props.radius - 5 px, height: pr…...
【ES6复习笔记】Promise对象详解(12)
1. 什么是 Promise? Promise 是 JavaScript 中处理异步操作的一种机制,它可以让异步操作更加容易管理和控制。Promise 对象代表一个异步操作的最终完成或失败,并提供了一种方式来处理操作的结果。 2. Promise 的基本语法 Promise 对象有三…...
前端Python应用指南(五)用FastAPI快速构建高性能API
《写给前端的python应用指南》系列: (一)快速构建 Web 服务器 - Flask vs Node.js 对比(二)深入Flask:理解Flask的应用结构与模块化设计(三)Django vs Flask:哪种框架适…...
c#多线程之生产者-消费者模型
在 C# 中实现 生产者-消费者模式,通常需要多个线程来处理数据的生产和消费。我们可以使用 Queue<T> 来作为存储数据的队列,并使用 Thread、Mutex 或 Monitor 来确保线程安全。BlockingCollection<T> 是 C# 提供的一个线程安全的集合…...
2011-2020年各省城镇职工基本医疗保险年末参保人数数据
2011-2020年各省城镇职工基本医疗保险年末参保人数数据 1、时间:2011-2020年 2、来源:国家统计局 3、指标:省份、时间、城镇职工基本医疗保险年末参保人数 4、范围:31省 5、指标解释:参保人数指报告期末按国家有关…...
Python基础语法知识——列表、字典、元组与集合
列表(list)、字典(dictionary)、元组(tuple)与集合(set)都可以看成存储数据的容器,但是前两者常用,后两者用得相对较少。 目录 1 列表(list) 1.1列表入门 1 列表(list) 1.1列表入门 class1["李白…...
Mysql数据库中,监测某张表中某字段的修改情况(被哪个ip所修改、新老值)
在Mysql数据库中,通过写一个触发器,来监测某张表(q_device)字段(run_status)的改变情况。 【示例】 -- 1. 创建监测日志表 CREATE TABLE change_log (id INT AUTO_INCREMENT PRIMARY KEY,table_name VARCHAR(255),column_name VARCHAR(255),old_value T…...
迁移学习 详解及应用示例
简介: 迁移学习是一种机器学习技术,其核心思想是利用在一个任务上已经学到的知识(源任务:任务已经有一个训练好的模型,然后我们将这个模型的某些部分或知识迁移到一个新的但相关的“目标任务”上。)来帮助解…...
ubuntu控制器多网口配置
在Ubuntu系统中配置多网口,可以通过编辑网络配置文件(Netplan 或旧版 /etc/network/interfaces)实现。这适用于需要管理多个网络接口(如 eth0、eth1 等)的场景,例如负载均衡、网络隔离或多路径通信。 以下…...
接口调用限频(代理模式+滑动窗口)
目录 代码示例 接口 代理 接口实现 限流工厂 限流处理器接口 直接交换处理器 限流处理器 限流配置 滑动窗口限流 通过代理模式滑动窗口,限流请求第三方平台,避免出现第三方平台抛出限流异常,影响正常业务流程,从出口出发…...
FFmpeg在python里推流被处理过的视频流
链式算法处理视频流 视频源是本地摄像头 # codinggbk # 本地摄像头直接推流到 RTMP 服务器 import cv2 import mediapipe as mp import subprocess as sp# 初始化 Mediapipe mp_drawing mp.solutions.drawing_utils mp_drawing_styles mp.solutions.drawing_styles mp_holis…...
2- Linux系统的命令帮助
Linux 命令行帮助信息使用指南 一、引言 对于初学者来说,Linux命令行可能会显得复杂和难以捉摸。然而,一旦掌握了如何有效地利用命令行的帮助信息,您将发现它是一个强大而灵活的工具,可以极大地提高您的工作效率。本指南旨在为新手介绍如何在Linux中获取命令的帮助信息,…...
Mysql事务
一、数据库事务基础 1.1. 什么是事务 简单来说,事务就是要保证一组数据库操作,要么全部成功,要么全部失败。在 MySQL 中,事务支持是在引擎层实现的。 比如 MySQL 原生的MyISAM引擎就不支持事务,这也是MyISAM被InnoDB…...
Fast adaptively balanced min-cut clustering
#0.论文信息 标题:Fast adaptively balanced min-cut clustering期刊:Pattern Recognition作者: Feiping Nie , Fangyuan Xie , Jingyu Wang ,Xuelong Li机构: China Telecom, Northwestern Polytechnic al University.代码链接: #1.摘要 …...
vue3和springboot使用websocket通信
前端端口:9090 后端端口:8080 vue3 引入依赖: npm install sockjs-client stomp/stompjs vue页面 <template><div><h1>WebSocket 示例</h1><button click"sendMessage">发送消息</button>…...
Log4j2的Policies详解、SizeBasedTriggeringPolicy、TimeBasedTriggeringPolicy
文章目录 一、Policies二、SizeBasedTriggeringPolicy:基于文件大小的滚动策略2.1、文件达到指定大小就归档 三、TimeBasedTriggeringPolicy:基于时间间隔的滚动策略3.1、验证秒钟归档场景3.2、验证分钟场景3.3、验证小时场景 四、多策略组合使用五、扩展知识5.1、S…...