leetcode414. 第三大的数

题目:

给你一个非空数组,返回此数组中 第三大的数 。如果不存在,则返回数组中最大的数。

示例 1:

输入:[3, 2, 1]
输出:1
解释:第三大的数是 1 。

示例 2:

输入:[1, 2]
输出:2
解释:第三大的数不存在, 所以返回最大的数 2 。

示例 3:

输入:[2, 2, 3, 1]
输出:1
解释:注意,要求返回第三大的数,是指在所有不同数字中排第三大的数。
此例中存在两个值为 2 的数,它们都排第二。在所有不同数字中排第三大的数为 1 。

提示:

  • 1 <= nums.length <= 104
  • -231 <= nums[i] <= 231 - 1

进阶:你能设计一个时间复杂度 O(n) 的解决方案吗?

思路:

把nums去重且排序,返回最后一个数或倒数第三个数即可。

代码:

class Solution {
public:int thirdMax(vector<int>& nums) {// 插入到set中实现自动去重和排序set<int> st;int i;for(i = 0; i < nums.size(); i++){st.insert(nums[i]);}nums.clear();// nums实现去重和排序for(set<int>::iterator it = st.begin(); it != st.end(); it++){nums.push_back(*it);}int max;if(nums.size() < 3){max = nums[nums.size()-1];}else {max = nums[nums.size()-3];}return max;}
};

emmm好吧我承认,这个写的有点复杂了

运行结果:

2023.8.19改良算法:

 

 该思路:

设置set,从前往后遍历,只维护size=3的set,如果大于3,则去除最小值。

class Solution {
public:int thirdMax(vector<int>& nums) {set<int> st;for(int i = 0; i < nums.size(); i++){st.insert(nums[i]);if(st.size() > 3){st.erase(st.begin());}}int max;set<int>::iterator it = st.begin();if(st.size() == 3){it = st.begin();max = *it;}else {it = st.end();max = *(--it);}return max;}
};

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

字符设备驱动实例(ADC驱动)

四、ADC驱动 ADC是将模拟信号转换为数字信号的转换器&#xff0c;在 Exynos4412 上有一个ADC&#xff0c;其主要的特性如下。 (1)量程为0~1.8V。 (2)精度有 10bit 和 12bit 可选。 (3)采样时钟最高为5MHz&#xff0c;转换速率最高为1MSPS (4)具有四路模拟输入&#xff0c;同一时…

【LVS集群】

目录 一、集群概述 1.负载均衡技术类型 2.负载均衡实现方式 二、LVS结构 1.三层结构 2.架构对象 三、LVS工作模式 四、LVS负载均衡算法 1.静态负载均衡 2.动态负载均衡 五、ipvsadm命令详解 1. -A 2. -D 3. -L 4. -a 5. -d 6. -l 7. -t 8. -s 9. -r 10. -…

css 实现四角边框样式

效果如图 此图只实现 左下与右下边角样式 右上与左上同理 /* 容器 */ .card-mini {position: relative; } /* 左下*/ .card-mini::before {content: ;position: absolute;left: 0;bottom: 0;width: 20px;height: 20px;border-bottom: 2px solid #253d64;border-left: 2px so…

redis 6个节点(3主3从),始终一个节点不能启动

redis节点&#xff0c;始终有一个节点不能启动起来 1.修改了配置文件 protected-mode no&#xff0c;重启 修改了配置文件 protected-mode no&#xff0c;重启redis问题依然存在 2、查看/var/log/message的redis日志 Aug 21 07:40:33 redisMaster kernel: Out of memory: K…

什么是神经网络

什么是神经网络 什么是神经网络&#xff1f;CNN、RNN、GNN&#xff0c;这么多的神经网络&#xff0c;有什么区别和联系&#xff1f; 既然我们的目标是打造人工智能&#xff0c;拥有智慧的大脑无疑是最好的模仿对象&#xff0c;人脑中有约860亿个神经元&#xff0c;这被认为是…

9 - 蓝图

蓝图: 将项目分成一个个单独的app模块&#xff0c;然后将所有app分配不同的处理功能&#xff0c;通过路由分配将它们连接成一个大项目 目录结构: 搭建框架: (1). 新键apps 包,编辑__init__.py文件 from flask import Flask import settings from apps.user.view import user_b…

03_缓存双写一致性

03——缓存双写一致性 一、缓存双写一致性 如果redis中有数据&#xff0c;需要和数据库中的值相同如果redis中无数据&#xff0c;数据库中的值要是最新值&#xff0c;且准备回写redis 缓存按照操作来分&#xff0c;可以分为两种&#xff1a; 只读缓存 读写缓存 同步直写操作…

构造不包含字母和数字的webshell

文章目录 利用不含字母与数字进行绕过知识介绍题目方法一&#xff1a;异或操作绕过方法二&#xff1a;取反进行绕过 过滤不是很严格的情况进阶绕过利用php7特性直接绕过 利用不含字母与数字进行绕过 知识介绍 <?phpecho "A"^"";?>从运行结果为! …

git拉取失败/git fatal终极解决方法

前言 被折磨不下20次总结出来的终极方案 步骤 0 首先关闭代理试试&#xff0c;不行就下一步 1 重置代理或者取消代理的方式 git config --global --unset http.proxy git config --global --unset https.proxy添加全局代理 git config --global http.proxy git config …

ubuntu 安装 postgresql以及 wal回滚

安装 sudo apt install postgresql postgresql-contrib设置远程连接 修改/etc/postgresql/12/main/postgresql.conf **将listen_addresses 改成 ***修改/etc/postgresql/12/main/pg_hba.conf 找到如下信息 #IPv4 local connections: 修改为 host all all 0.0.0.0/0 md5 重启…

Apache ShenYu 学习笔记一

1、简介 这是一个异步的&#xff0c;高性能的&#xff0c;跨语言的&#xff0c;响应式的 API 网关。 官网文档&#xff1a;Apache ShenYu 介绍 | Apache ShenYu仓库地址&#xff1a;GitHub - apache/shenyu: Apache ShenYu is a Java native API Gateway for service proxy, pr…

(6)(6.2) 任务命令

文章目录 前言 6.2.1 概述 6.2.2 导航命令 6.2.3 条件命令 6.2.4 DO命令 前言 本文介绍了 Copter、Plane 和 Rover 切换到自动模式时支持的任务指令。 &#xff01;Warning 这是一项正在进行中的工作&#xff0c;尚未经过全面审核。有关 Copter 的更佳列表&#xff0c;请…

docker搭建私有镜像harbor

docker安装搭建私有仓库 Harbor harbor用于存储和分布docker镜像企业级registry服务器的harbor使用的是官方的docker registry(v2命名是distribution)服务去完成。 安装harhor 启动harbor 6.

【C++】红黑树

目录 一、红黑树的概念二、红黑树的性质三、红黑树的插入操作四、红黑树的验证五、红黑树和AVL树的比较六、代码 一、红黑树的概念 红黑树&#xff0c;是一种二叉搜索树&#xff0c;但在每个结点上增加一个存储位表示结点的颜色&#xff0c;可以是Red或Black。 通过对任何一条从…

k8s容器加入host解析字段

一、通过edit或path来修改 kubectl edit deploy /xxxxx. x-n cattle-system xxxxx为你的资源对象名称 二、添加字段 三、code hostAliases:- hostnames:- www.rancher.localip: 10.10.2.180

Python爬虫实战案例——第二例

某某美剧剧集下载(从搜索片名开始) 本篇文章主要是为大家提供某些电影网站的较常规的下载电影的分析思路与代码思路(通过爬虫下载电影)&#xff0c;我们会从搜索某部影片的关键字开始直到成功下载某一部电影。 地址&#xff1a;aHR0cHM6Ly93d3cuOTltZWlqdXR0LmNvbS9pbmRleC5od…

简单理解Socket

TCP/IP 要想理解socket首先得熟悉一下TCP/IP协议族&#xff0c; TCP/IP&#xff08;Transmission Control Protocol/Internet Protocol&#xff09;即传输控制协议/网间协议&#xff0c;定义了主机如何连入因特网及数据如何再它们之间传输的标准&#xff0c; 从字面意思来看T…

《剑指Offer》模块三 思维题【面试官可能考的13道思维算法题】

思维题 1. 扑克牌的顺子【思维题】 原题链接 1. 判断所有牌中 是否出现 重复 2. 有序sort后 判断是否最大差距 <4 class Solution { public:bool isContinuous( vector<int> nums) {sort(nums.begin(), nums.end());for (int i 1; i < nums.size(); i )if …

js使用for of遍历map

//使用for of遍历map console.log("---") console.log(odata.studentDetails) let obj odata.studentDetails[0].answerSituation for(let [key,value] of Object.entries(obj)){console.log(value) }

【业务功能篇73】web系统架构演变-单体-集群-垂直化-服务化-微服务化

1.服务架构的演 1.1 单体架构 单体架构应该是我们最先接触到的架构实现了&#xff0c;在单体架构中使用经典的三层模型&#xff0c;即表现层&#xff0c;业务逻辑层和数据访问层。 单体架构只适合在应用初期&#xff0c;且访问量比较下的情况下使用&#xff0c;优点是性价比很…